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

PROBLEM

难度困难

MY ANSWER

无，以为有O(n)解法。

BETTER SOLUTION

归并排序的同时进行逆序对的计算，时间复杂度O(nlogn)，空间复杂度O(n)。

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return mergeSort(0, nums.size() - 1, nums, tmp);
    }
private:
    int mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m, nums, tmp) + mergeSort(m + 1, r, nums, tmp);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = nums[k];
        for (int k = l; k <= r; k++) {
            if (i == m + 1)
                nums[k] = tmp[j++];
            else if (j == r + 1 || tmp[i] <= tmp[j])
                nums[k] = tmp[i++];
            else {
                nums[k] = tmp[j++];
                res += m - i + 1; // 统计逆序对
            }
        }
        return res;
    }
};

SUMMARY

归并排序模板

vector<int> nums;			\\排序数组
vector<int> tmp;			\\辅助数组
void mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp) {
    // 终止条件
    if(l >= r) {
        return;
    }
    // 递归划分
    int m = (l + r) / 2;
    mergeSort(l, m, nums, tmp);
    mergeSort(m+1, r, nums, tmp);
    // 合并阶段
    int lp = l, rp = m + 1;
    for(int i = l; i <= r; i++) {
        tmp[i] = nums[i];
    }
    for(int i = l; i <= r; i++) {
        if(lp == m + 1) {
            nums[i] = tmp[rp++];
        }
        else if(rp == r + 1 || tmp[lp] <= tmp[rp]) {
            nums[i] = tmp[lp++];
        }
        else {
            nums[i] = tmp[rp++];
        }
    }
}