数组中的逆序对.md

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

示例 
输入: [7,5,6,4]
输出: 5

分析：以分治、归并排序的思想去找所有的逆序对。将原问题分解成两部分，左区间中对逆序对、右区间中对逆序对、中间部分对逆序对。

    [7,5,6,4]
   [7,5] [6,4]
 [7] [5] [6] [4]

1. 当只有一个元素时，逆序对为0。
2. 归并排序两个长度为1的区间，左右各自的逆序对都为0，此时计算处于中间部分存在的逆序对。
   • 中间部分存在对逆序对指左右两个区间归并时存在对逆序对，当右区间的元素进入辅助数组时，此时存在的逆序对为左边区间中未归并的元素的个数。其余情况均可不计入逆序对。
3. 归并排序两个小区间并同时记录上一步计算的逆序对的个数。此时两个区间为[5 7](逆序对为1)和[4 6](逆序对为1)。
4. 再以相同规则归并以上两个区间，各自区间对逆序对个数已经有了，求中间部分的逆序对。

        [ 5 7] [4 6] (逆序对count=1+1=2)
#1 指针   i      j    (此时右区间元素小，逆序对加做区间未归并的元素个数:count+=2=4)
#2 指针   i        j  (此时左区间元素小，正常归并)
#3 指针      i     j  (此时右区间小，同第一步，count+=1=5)
#4 右区间遍历结束，归并左区间剩下的元素即可。

时间复杂度：归并排序的时间负责度O(NlogN) 空间复杂度：O(n)

C++代码

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int length = nums.size();
        if(length < 2) {
            return 0;
        }
        vector<int> tmp(length);
        return CountReversePairs(nums,tmp,0,length-1);
    }

    //这是找左右各自的逆序对的，到一个元素，自然为0，当两个元素的时候，如果有序，则直接返回，如果无需则考虑中间存在的逆序对
    int CountReversePairs(vector<int>& nums,vector<int> &tmp,int left,int right){
        if(left >= right) {
            return 0;
        }
        int mid = left + (right-left)/2;
        int leftPairs = CountReversePairs(nums,tmp,left,mid);
        int rightPairs = CountReversePairs(nums,tmp,mid+1,right); 
        int pairs = leftPairs + rightPairs;
        if(nums[mid] <= nums[mid+1]) {
            return pairs;
        }
        int centerPairs = mergeCount(nums,tmp,left,mid,right);
        return centerPairs+pairs;
    }

    //左右都有序
    int mergeCount(vector<int>& nums,vector<int> &tmp,int left,int mid,int right){
        int count = 0;
        int l = left,leftEnd = mid,r = mid+1,rightEnd = right;
        int p = left;
        while(l<=leftEnd && r<= rightEnd){
            if(nums[l] > nums[r]){
                count+= (mid-l+1);    
                tmp[p++] = nums[r++];
            }else{
                tmp[p++] = nums[l++];
            }
        }
        while(l<=leftEnd) {
            tmp[p++] = nums[l++];
        }
        while(r<=rightEnd) {
            tmp[p++] = nums[r++];
        }
        for(int i = left; i <= right; i++ ){
            nums[i] = tmp[i];
        }
        return count;
    }
};

class Solution {
public:

    static const int N = 50010;
    int tmp[N];
    int merge_sort(vector<int> &nums, int l, int r ){
        if(l>=r) return 0;
        int mid = l + r >> 1;
        int res = 0;
        res += merge_sort(nums, l, mid);
        res += merge_sort(nums, mid+1, r);
        int k = 0;
        int i = l, j = mid+1;
        while(i<=mid && j <= r) {
            if(nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            }
            else {
                int count = mid - i + 1;
                res += count;
                tmp[k++] = nums[j++];
            }
        }
        while(i<=mid) tmp[k++] = nums[i++];
        while(j<=r) tmp[k++] = nums[j++];
        for(int i = l, k = 0; i<= r; i++,k++){
            nums[i] = tmp[k];
        }
        return res;
    }

    int reversePairs(vector<int>& nums) {
        int n = nums.size();

        int res = merge_sort(nums, 0, n-1);

        return res;
    }
};