面试题36：数组中的逆序对（归并排序思想）

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。例如，有一个数组为Array[0..n] 其中有元素a[i]，a[j].如果当i<j时，a[i]>a[j],那么我们就称（a[i],a[j]）为一个逆序对。在数组{7,5,6,4}中一共存在5对逆序对，分别是(7,6),(7,5),(7,4),(6,4),(5,4)。

最简单的想法就是遍历每一个元素，让其与后面的元素对比，如果大于则count++，但是这样的时间复杂度是o(n2)。这题有更好的解决方法，时间复杂度只需要o(nlogn)。其实这道题目的思路跟归并排序差不多，求逆序对的过程就是一个求归并排序的过程，在求出逆序对以后，原数组变得有序，是通过归并排序得到的。

代码中31行之后相当于归并排序的Merge函数，作用是求两个归并序列归并后存在的逆序对

 1 int InversePairsCore(int* data, int* copy, int start, int end);
 2 
 3 int InversePairs(int* data, int length)
 4 {
 5     if(data == NULL || length < 0)
 6         return 0;
 7 
 8     int* copy = new int[length];
 9     for(int i = 0; i < length; ++ i)
10         copy[i] = data[i];
11 
12     int count = InversePairsCore(data, copy, 0, length - 1);
13     delete[] copy;
14 
15     return count;
16 }
17 
18 int InversePairsCore(int* data, int* copy, int start, int end)
19 {
20     if(start == end)
21     {
22         copy[start] = data[start];
23         return 0;
24     }
25 
26     int length = (end - start) / 2;
27 
28     int left = InversePairsCore(copy, data, start, start + length);
29     int right = InversePairsCore(copy, data, start + length + 1, end);
30 
31     // i初始化为前半段最后一个数字的下标
32     int i = start + length; 
33     // j初始化为后半段最后一个数字的下标
34     int j = end; 
35     int indexCopy = end;
36     int count = 0;
37     while(i >= start && j >= start + length + 1)
38     {
39         if(data[i] > data[j])
40         {
41             copy[indexCopy--] = data[i--];
42             count += j - start - length;
43         }
44         else
45         {
46             copy[indexCopy--] = data[j--];
47         }
48     }
49 
50     for(; i >= start; --i)
51         copy[indexCopy--] = data[i];
52 
53     for(; j >= start + length + 1; --j)
54         copy[indexCopy--] = data[j];
55 
56     return left + right + count;
57 }

面试题36：数组中的逆序对（归并排序思想）

相关推荐