剑指offer:数组中的逆序对

题目描述

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

class Solution {
public:
    int InversePairs(vector<int> data) {

        int len = data.size();

        if (len == 0){
            return 0;
        }

        vector<int> tmp(len);

        int res = mergeSort(data, tmp, 0, len - 1);

        return res;
    }

private:

    int mergeSort(vector<int> &data, vector<int> &tmp, int left, int right){

        if (left == right){
            return 0;
        }

        int mid = left + (right - left) / 2;

        int leftCnt = mergeSort(data, tmp, left, mid);
        int rightCnt = mergeSort(data, tmp, mid + 1, right);

        int i = mid;
        int j = right;
        int tmpIndex = right;

        int cnt = 0;

        while (i >= left && j >= mid + 1){
            if (data[i] > data[j]){
                tmp[tmpIndex--] = data[i--];
                //难点是怎么算cnt
                cnt += j - mid;
            }
            else{
                tmp[tmpIndex--] = data[j--];
            }
        }

        for (; i >= left; i--){
            tmp[tmpIndex--] = data[i--];
        }

        for (; j >= mid + 1; j--){
            tmp[tmpIndex--] = data[j--];
        }

        for (int i = left; i <= right; i++){
            data[i] = tmp[i];
        }

        return leftCnt + rightCnt + cnt;
    }


};