面试题 51：数组中的逆序对.md

试题链接：65. 数组中的逆序对 - AcWing题库

方法一：暴力

• 思路：使用双重循环遍历所有可能的数对计算逆序对。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

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

方法二：归并排序

• 思路：一个区间的逆序对数目等于前半个区间的逆序对个数+后半个区间的逆序对个数+后半个区间中每个数在前半个区间中有多少个比它大的数的总和，前面两部分可以递归获取，最后一部分可以在合并两个有序区间的时候快速得到，对于前半个区间中的 i，如果它大于后半个区间的 j，那么从 i 到前半个区间的最后一个数都是大于 j 的。
• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

class Solution {
public:
    int inversePairs(vector<int>& nums) {
        int n = nums.size();
        tmp.resize(n);
        return mergeSort(nums, 0, n - 1);
    }
    
    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;
        
        int cnt = 0;
        
        int mid = (left + right) / 2;
        
        cnt += mergeSort(nums, left, mid);
        cnt += mergeSort(nums, mid + 1, right);
        
        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                cnt += mid - i + 1;
                tmp[k++] = nums[j++];
            }
        }
        
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= right) tmp[k++] = nums[j++];
        
        for (int i = left; i <= right; i++) nums[i] = tmp[i];
        
        return cnt;
    }

private:
    vector<int> tmp;
};

方法三：离散化树状数组

• 思路：树状数组支持动态维护前缀和，因此我们可以用树状数组维护每个数的出现次数，倒序遍历，当遍历原数组中的 i 时，通过数组求得树状数组中小于当前元素的数的个数。但是由于数可能很大，因此开一个很大的树状数组不现实，因此可以使用离散化的方式，我们只关注相对大小。离散化后将原数组元素改为离散化数组中的索引，由于树状数组中计算的是 1 ~ x 的前缀和，故下标 + 1，从 1 开始。
• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

class Solution {
public:
    int inversePairs(vector<int>& nums) {
        // 离散化
        vector<int> tmp = nums;
        sort(tmp.begin(), tmp.end());
        tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
        
        for (int& num : nums) {
            num = lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() + 1;
        }
        
        cn = tmp.size() + 1;
        c.resize(cn);
        
        int ans = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            ans += query(nums[i] - 1);
            add(nums[i], 1);
        }
        
        return ans;
    }
    
    void add(int i, int x) {
        while (i < cn) {
            c[i] += x;
            i += i & -i;
        }
    }
    
    int query(int i) {
        int sum = 0;
        while (i) {
            sum += c[i];
            i -= i & -i;
        }
        return sum;
    }
    
private:
    int cn;
    vector<int> c;
};