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

方法一：归并排序

解题思路

逆序对：即后面的数大于前面的数；
归并排序：

先分，在此过程中会先递归的将序列分为一段一段序列，并且每段序列之间的先后顺序是不变的。
再治，也即归并，归并的过程中会将两段序列进行比较\(（A，B，B在A的后面）\)，当出现\(B\)中的数小于\(A\)中的某个数时，则也小于\(A\)中后面的所有数，出现逆序对。

代码

class Solution {
public:
    int mergeSort(vector<int>& nums, int l, int r) {
        if (l >= r) return 0;
        int mid = l + r >> 1;
        int res = 0;
        // 分治
        res =  mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r); 
        // 归并
        vector<int> tmp(r - l + 1); 
        int idx = 0, st0 = l, ed0 = mid, st1 = mid + 1, ed1 = r; // 0表示左边数组，1表示右边数组
        while (st0 <= ed0 && st1 <= ed1) {
            if (nums[st0] <= nums[st1]) {
                tmp[idx] = nums[st0 ++ ];
            } else { // 当的右边数组元素小于左边数组元素时，即出现逆序情况，且由于左边数组有序，则比左边数组的所有元素都小
                tmp[idx] = nums[st1 ++ ];
                res += ed0 - st0 + 1;
            }
            idx ++ ;
        }
        while (st0 <= ed0) {
            tmp[idx] = nums[st0 ++ ];
            idx ++ ;
        }
        while (st1 <= ed1) {
            tmp[idx] = nums[st1 ++ ];
            idx ++ ;
        }
        // 替换原数组中的元素
        for (int i = l, j = 0; i <= r; i ++, j ++ ) {
            nums[i] = tmp[j];
        }
        return res; 
    }
    int reversePairs(vector<int>& nums) {
        if (nums.size() <= 1) return 0;
        return mergeSort(nums, 0, nums.size() - 1);
    }
};

复杂度分析

时间复杂度：\(O(nlogn)；\)
空间复杂度：\(O(n)。\)

方法二：离散化 + 树状数组

前题知识一：离散化

当对于一组数据其值相对较大时，那么直接针对对其值大小建立\(hash\)表时，会浪费很多额外的空间，那么我们可以将其每一个值转换为其在所有数值中的次序，然后直接建立\(hash[n + 1]\)，\(n\)为数据量。转换操作通过二分查找实现。

前题知识二：树状数组

参考：『 4种解法一网打尽』有序数组、归并排序、树状数组和线段树的实现及注释
注意：在本题中树状数组主要优化前缀和的计算以及更新，当某个位置的值更新时，可以在\(O(logn)\)的时间复杂度内更新新的前缀和数组。

解题思路

从后往前遍历原数组，对于\(nums[i]\)，找\(nums[i + 1, n - 1]\)中比其小的元素，现在就是要简化找的过程！！！

我们对离散化后的数组\(nums\)（存储的为原来元素的次序），从后向前遍历，当遍历到\(nums[i]\)时：

\(ans += query(nums[i] - 1)\)，加上当前比\(nums[i]\)小的所有元素个数（前缀和计算），因为此时的\(Tree\)数组，是由之前的元素（即当前元素右边的元素）\(insert()\)得来，当出现比\(nums[i]\)小的元素，说明出现右边的元素小于左边的元素，即逆序对。
然后更新\(Tree\)数组，\(insert(num[i])\)（前缀和更新），方便后续元素计算逆序对。

代码

class BIT {
private:
    vector<int> Tree;
    int n;
public:
    BIT(int _n) : n(_n), Tree(_n + 1) {}
    static int lowbit(int x) {
        return x & (-x);
    }
    int query(int x) {
        int res = 0;
        while (x) {
            res += Tree[x];
            x -= lowbit(x);
        }
        return res;
    }
    void insert(int x, int value) {
        while (x <= n) {
            Tree[x] += value;
            x += lowbit(x);
        }
    }
};

class Solution {
public:
    int find(int x, vector<int>& alls) { // 找到第一个大于等于x的位置
        int l = 0, r = alls.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (alls[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return r + 1; // 映射到1, 2, ...n
    }
    void Discrete(vector<int>& nums) { // 离散化后nums[i]存储的是之前值在nums中的次序（从小到大）
        vector<int> alls = nums;
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
        for (auto &num : nums) {
            num = find(num, alls); // 下标从1开始
        }
    }
    int reversePairs(vector<int>& nums) {
        Discrete(nums);
        BIT tree(nums.size());
        int ans = 0;
        for (int i = nums.size() - 1; i >= 0; i -- ) {
            ans += tree.query(nums[i] - 1); // 计算原数组nums[i]右边比它小（即Tree中的下标）的元素的个数
            tree.insert(nums[i], 1);
        }
        return ans;
    }
};