剑指offer 36 数组中的逆序对

转载请注明出处：http://blog.csdn.net/ns_code/article/details/27520535

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。输入：

每个测试案例包括两行：

第一行包含一个整数n，表示数组中的元素个数。其中1 <= n <= 10^5。

第二行包含n个整数，每个数组均为int类型。

输出：对应每个测试案例，输出一个整数，表示数组中的逆序对的总数。样例输入：

4
7 5 6 4

样例输出：

5

    思路：最简单的方法是顺序数组，将每个数字与后面的比较，统计逆序对的个数，这种方法的时间复杂度为O(n*n)，这种方法写出的代码在九度OJ上测试，会超时。剑指offer给出了归并排序的思路，这个有点难想到啊，也可能是我太弱了，根本没往这方面想！理解了思路，就不难了，将数组划分成两个子数组，再将子数组分别划分成两个子数组，统计每个子数组内的逆序对个数，并将其归并排序，再统计两个子数组之间的逆序对个数，并进行归并排序。这就是归并排序的变种，在归并排序代码的基础上稍作改进即可。

    合理还要注意一点：全局变量count不能声明为int型，必须为long long型。因为题目中说数组最大为10^5，那么最大逆序对为(10^5-1)*10^5/2，这个数大约在50亿左右，超过了int型的表示范围。

    AC代码如下：

[cpp] view plaincopy

1. #include<stdio.h>
2. #include<stdlib.h>
4. /*
5. 统计两个子数组之间的逆序对
6. */
7. long long MergePairsBetweenArray(int *arr,int *brr,int start,int mid,int end)  
8. {  
9. int i = mid;  
10. int j = end;  
11. int k = end;  //辅助数组的最后一位
12. long long count = 0;  
14. //设置两个指针i,j分别从右往左依次比较，
15. //将较大的依次放入辅助数组的右边
16. while(i>=start && j>=mid+1)  
17.     {  
18. if(arr[i] > arr[j])  
19.         {  
20.             count += j-mid;  
21.             brr[k--] = arr[i--];  
22.         }  
23. else
24.             brr[k--] = arr[j--];  
25.     }  
27. //将其中一个数组中还剩下的元素拷贝到辅助数组中，
28. //两个循环只会执行其中的一个
29. while(i>=start)  
30.         brr[k--] = arr[i--];  
31. while(j>=mid+1)  
32.         brr[k--] = arr[j--];  
34. //从辅助数组中将元素拷贝到原数组中，使其有序排列
35. for(i=end;i>k;i--)  
36.         arr[i] = brr[i];  
38. return count;  
39. }  
41. /*
42. 统计数组中的所有的逆序对
43. */
44. long long CountMergePairs(int *arr,int *brr,int start,int end)  
45. {  
46. long long PairsNum = 0;  
47. if(start<end)  
48.     {  
49. int mid = (start+end)>>1;  
50.         PairsNum += CountMergePairs(arr,brr,start,mid); //统计左边子数组的逆序对
51.         PairsNum += CountMergePairs(arr,brr,mid+1,end); //统计右边子数组的逆序对
52.         PairsNum += MergePairsBetweenArray(arr,brr,start,mid,end); //统计左右子数组间的逆序对
53.     }  
54. return PairsNum;  
55. }  
57. /*
58. 将函数封装起来
59. */
60. long long CountTotalPairs(int *arr,int len)  
61. {  
62. if(arr==NULL || len<2)  
63. return 0;  
65. int *brr = (int *)malloc(len*sizeof(int));  
66. if(brr == NULL)  
67.         exit(EXIT_FAILURE);  
69. long long sum = CountMergePairs(arr,brr,0,len-1);  
70.     free(brr);  
71.     brr = NULL;  
73. return sum;  
74. }  
76. int main()  
77. {  
78. int n;  
79. while(scanf("%d",&n) != EOF)  
80.     {  
81. int *arr = (int *)malloc(n*sizeof(int));  
82. if(arr == NULL)  
83.             exit(EXIT_FAILURE);  
85. int i;  
86. for(i=0;i<n;i++)  
87.             scanf("%d",arr+i);  
89.         printf("%lld\n",CountTotalPairs(arr,n));  
91.         free(arr);  
92.         arr = NULL;  
93.     }  
94. return 0;  
95. }  

/**************************************************************

Problem: 1348

User: mmc_maodun

Language: C

Result: Accepted

Time:100 ms

Memory:1696 kb

****************************************************************/