LeetCode: 数组的点逆序对

[guodongxiaren]

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

  示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

---

出自剑指Offer：51

[guodongxiaren]

解法两种：

• 归并排序
• 树状数组

官方题解：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/

[guodongxiaren]

归并排序解法

class Solution {
public:

    int cnt = 0;
    int merged[50001];
    void merge_sort(int left, int right, vector<int>& A) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        //int mid = left + (right - left) / 2;
        merge_sort(left, mid, A);
        merge_sort(mid+1, right, A);

        // 这是一处优化，也可以去掉
        if (A[mid] <= A[mid+1]) {
            return;
        }

        int pl = left, pr = mid+1, pm = 0; 

        while (pl <= mid && pr <= right) {
            if (A[pl] <= A[pr]) {
                merged[pm++] = A[pl++];
            } else {
                merged[pm++] = A[pr++];
                cnt += mid - pl + 1; // 去掉这句就是普通的归并排序
            }
        }
        while (pl <= mid) {
            merged[pm++] = A[pl++];
        }
        while (pr <=right) {
            merged[pm++] = A[pr++];
        };
        for (int i = 0; i < pm; i++) {
            // 给原数组相应的部分排好序
            A[i + left] = merged[i];
        }
    }
    int reversePairs(vector<int>& nums) {
        merge_sort(0, nums.size() -1, nums);
        return cnt;
    }
};

题目之外的三个要点：

1. mid怎么求？

本题 mid = (left + right)/ 2; 可以。 但是left + right有溢出的风险。 历史上好像有个案例，某个二分法出现过bug。

Java有 >>> 无符号右移。C++没有。

通用的解决方案是：mid = left + (right - left) / 2;

2. 归并排序有稳定和不稳定两种实现

<=是稳定排序，<是不稳定排序。

3. 优化

连续的两个递归调用merge_sort是在分解。后面的逻辑是合并。 两个merge_sort调用完，[left, mid] [mid+1, right]两个区间已经各自有序。 如果A[mid] < A[mid+1]那么此时[left, right]也已经整体有序，不会再产生新的逆序对，也不需要再执行下面的合并逻辑！

        if (A[mid] <= A[mid+1]) {
            return;
        }

[guodongxiaren]

TODO

树状数组