【剑指offer】求逆序对的个数

2013-09-07 10:50:31

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

小结：

最直观的的方法是：对每个数字，测试后面的数字是否小于该数字，这种方法的时间复杂度为O(N^2)；
为了改善时间性能，用归并的方法，但这种方法组要辅助的空间O(N)，见下面函数GetNumberOfInversePairs。

代码（测试暂未发现错误，欢迎交流指正！）：

 1 #include <iostream>
 2 #include <cassert>
 3 using namespace std;
 4 
 5 typedef int DataType;
 6 const int SIZE = 100;
 7 
 8 //归并，返回逆序的个数
 9 int Merge(DataType *array,int begin,int mid,int end)
10 {
11     int resLength = end - begin + 1;
12     DataType *resArray = new DataType[resLength];
13 
14     int index1 = mid;
15     int index2 = end;
16 
17     int cntOfInversePairs = 0;
18 
19     while (index1 >= begin && index2 >= (mid + 1))
20     {
21         if (array[index1] > array[index2])
22         {
23             resArray[--resLength] = array[index1--];
24             cntOfInversePairs += (index2 - mid);    //逆序的个数为第二个数组中剩余的数字个数
25         }
26         else
27         {
28             resArray[--resLength] = array[index2--];
29         }
30     }
31 
32     while (index1 >= begin)
33     {
34         resArray[--resLength] = array[index1--];
35     }
36 
37     while (index2 >= (mid + 1))
38     {
39         resArray[--resLength] = array[index2--];
40     }
41 
42     index1 = begin;
43     index2 = 0;
44       
45     while (index1 <= end)   //将排序后的数组复制到原数组中
46     {
47         array[index1++] = resArray[index2++];
48     }
49 
50     delete [] resArray;
51     return cntOfInversePairs;
52 }
53 
54 //递归求逆序对的个数
55 int GetNumberOfInversePairsRecursive(DataType *array,int begin,int end)
56 {
57     if (begin >= end)
58     {
59         return 0;
60     }
61 
62     int mid = begin + (end - begin) / 2;
63 
64     int cnt1 = GetNumberOfInversePairsRecursive(array,begin,mid);
65     int cnt2 = GetNumberOfInversePairsRecursive(array,mid + 1,end);
66 
67     int cnt3 = Merge(array,begin,mid,end);
68 
69     return (cnt1 + cnt2 + cnt3);
70 }
71 
72 //返回逆序对的个数
73 int GetNumberOfInversePairs(DataType *array,int len)
74 {
75     assert(array != NULL);
76     assert(len >= 1);
77 
78     return GetNumberOfInversePairsRecursive(array,0,len - 1);
79 }
80 
81 //测试GetNumberOfInversePairs()
82 void TestGetNumberOfInversePairs()
83 {
84     DataType array[SIZE] = {6,5,6,7};
85     int len = 4;
86 
87     cout<<"GetNumberOfInversePairs = "<<GetNumberOfInversePairs(array,len)<<endl;;
88 }
89 
90 int main()
91 {
92     TestGetNumberOfInversePairs();
93     return 0;
94 }

【剑指offer】求逆序对的个数

推荐阅读