剑指 Offer 51. 数组中的逆序对

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4] 输出: 5 限制：0 <= 数组长度 <= 50000

解题思路

1、直接使用暴力的方法 (遍历数组，不断比较后面的数字是否比当前的数字小，并计数) 会超时，复杂度
2、可以借鉴归并排序，在数组合并过程中，进行元素大小比较的时候统计逆序对个数，由于归并排序算法复杂度为 ，因此此算法复杂度也为 。

如何统计逆序对个数？
当在归并数组 ,区间 和区间 时 ， ( 用下标 指向前半区间, 指向后半区间 )
当 时，逆序个数加一，元素 首先合并到有序数组中去，接下来 的游标会往后移， 和 进行比较…….
但是注意如果 后面还有其他元素的化，因为 已经被移到有序数组中去了，所以 后面的元素没有机会再和它进行比较了，又由于数组的前半区间和后半区间是分别有序的，因为有： ，所以必有
，从而如果仅仅加一会导致我们没有漏掉一些逆序个数。
为使不漏，应加上包括 在内的其后面的前半区间元素个数，即

代码实现

class Solution {
public:
    int res = 0;
    int reversePairs(vector<int>& nums) {
        int size = nums.size();
        int left = 0 ;
        int right = size - 1;
        vector<int> tempnums(size);
        divide(nums,tempnums,left,right);
        return res;
    }
void divide(vector<int>& nums,vector<int>& tempnums,int left,int right) {
    if(left >= right )
        return;
    int mid = left + ((right - left) >> 1);
    divide(nums,tempnums,left,mid);
    divide(nums,tempnums,mid+1,right);
    //合并两个数组  merge(left,mid,right);
    int i = left, p = left;
    int j = mid + 1;
    while(i <= mid && j <= right) {
        if( nums[i] <= nums[j]){
            tempnums[p++] = nums[i++];
        }else{
             tempnums[p++] = nums[j++];
            /*
              nums[i] > nums[j],则 nums[i]后面的数都大于nums[j]
              在这里的时候要统计上，否则nums[j]被合并到有序数组中去了，后面不会再被比较到
            */
             res = res + (mid - i + 1);
        }
    }
    while(i <= mid){
        tempnums[p++] = nums[i++];
    }
    while(j <= right){
        tempnums[p++] = nums[j++];
    }
    copy(tempnums.begin()+left, tempnums.begin()+right+1, nums.begin()+left); 
}
};

**