剑指offer 53- 数组中的逆序对

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

输入一个数组，求出这个数组中的逆序对的总数。
样例

输入：[1,2,3,4,5,6,0]

输出：6

分析：

算法一：
直接暴力
时间复杂度

class Solution {
public:
    int inversePairs(vector<int>& nums) {
        if(!nums.size()) return 0;
        int res;
        for (int i=0; i<nums.size(); i++)
            for(int j=i+1; j<nums.size(); j++)
                if(nums[i] > nums[j]) res ++;
        return res;
    }
};

算法二：使用归并排序
时间复杂度：

class Solution {
public:
    int merge(vector<int>& nums, int l, int r) {
        if(l >= r) return 0;//只有一个元素
        int mid = l + r >> 1;
        int res = merge(nums, l, mid) + merge(nums, mid+1, r);//计算左右两个区间中的逆序对
        vector<int> temp;
        int i = l, j = mid+1;
        while(i<= mid && j<=r) {
            if(nums[i] <= nums[j]) temp.push_back(nums[i++]);
            else {
                temp.push_back(nums[j++]);//后面的元素小于前面的元素
                res += mid - i + 1;//i之后一直到mid的所以圆元素都比j元素大
            }
        }
        //无论是i或者是j，元素都比之前的数组要大，所以不可能存在新的逆序，把数组填好就可以了
        while(i<=mid) temp.push_back(nums[i++]);
        while(j<=r) temp.push_back(nums[j++]);
        
        i = l;
        for(auto x : temp) nums[i++] = x;
        return res;
    }
    int inversePairs(vector<int>& nums) {
        return merge(nums, 0, nums.size()-1);
    }
};