[刷题]剑指offer之逆序对的个数

题目

题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。

输入

描述

题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

示例

1,2,3,4,5,6,7,0 结果是 7

思路

一看到这个题我就感觉似曾相识，知道需要使用归并排序的思想来做，却早已忘记了归并排序的思想到底是什么。。。于是特地整理了一遍，见博客归并排序算法。

在归并排序的归并步骤时，可以顺便统计逆序对的个数。

图一.png

假设正在归并上面的数组，左侧的2，3，6，8和右侧的1，4，5，7已经排好序了，左侧和右侧内部都没有逆序对，而从左侧取一个数，从右侧取一个数，则有可能形成逆序对。

例如，开始左侧拿出2，右侧拿出1，可知2>1，形成了逆序对。此时逆序对只是加1吗？并不是，因为2右边的数都是大于2的，所以可以判断左边的数和右边的1可以形成4对逆序对（(2,1)、(3,1)、(6,1)、(8,1)）。

接下来比2和4，不会形成逆序对。再比3和4，不会形成逆序对。

当比较到6和4的时候，形成了逆序对，个数为2((6,4)、(8,4))。

图二.png

归纳一下，也就是在归并的时候，如果右侧的元素小于左侧的元素，这个时候开始统计逆序对就行了，如果左侧的索引为i，左侧的末尾元素的索引为mid，逆序对个数就为mid-i+1。

这样并没有结束，前面的假设是左侧和右侧是有序的，事实上并不是，左侧和右侧也进行了归并的过程才能变得有序，而在归并过程中，也能计算出逆序对的个数。

所以：

总的逆序对的个数=左侧归并时求得的逆序对个数 + 右侧归并时求得的逆序对个数 + 对整体进行归并时的逆序对个数。

可能会怀疑这三种情况会有重复，但是并没有。左侧归并找到的逆序对相当于从左侧数组中取2个数，而整体归并的时候是分别从左右数组中取1个数，不可能发生重复！

代码

知道上面的思路后，可以很容易的将归并排序代码进行修改。

class Solution {
public:
    int res;
    int InversePairs(vector<int> data) {
        vector<int> aux = data; //辅助空间
        return mergeSort(data, aux);
    }

    int mergeSort(vector<int> &arr, vector<int> &aux)
    {
        int n = (int)arr.size();
        return __mergeSort(arr, aux, 0, n-1);
    }

    // [l, r]
    int __mergeSort(vector<int> &arr, vector<int> &aux, int l, int r){
        if(l >= r)
            return 0;

        int mid = l + (r-l)/2;
        int left = __mergeSort(arr, aux, l, mid) % 1000000007;
        int right = __mergeSort(arr, aux, mid+1, r) % 1000000007;
        return (left + right + __merge(arr, aux, l, mid, r) )% 1000000007;

    }

    int __merge(vector<int> &arr, vector<int> &aux, int l, int mid, int r) {
        for( int i = l ; i <= r; i ++ )
            aux[i] = arr[i];

        int res = 0;
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid+1;
        for( int k = l ; k <= r; k ++ ){
            if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j];
                j ++;
            }
            else if( j > r ){  // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i];
                i ++;
            }
            else if( aux[i] < aux[j] ) {  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i];
                i ++;
            }
            else{  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j];
                j ++;
                res += (mid-i+1);
                res %= 1000000007;
            }
        }
        return res;
    }
};

总结

求逆序对是对归并排序思想的经典应用，很巧妙。求逆序对好像还有树状数组的方法，精力不够，掌握一种方法足够了。

我的SegmentFault链接

参考

剑指offer第二版--面试题51

归并排序算法