分治归并排序算法解析及经典题目实战

3. 交易逆序对的总数

题目描述：

示例：

交易逆序对的总数

题解：

因为归并排序的'分治 + 有序合并'特性，完美匹配逆序对统计的核心需求 —— 高效拆分问题、批量计算逆序对，这是暴力枚举做不到的。当 [left,mid] 和 [mid+1,right] 进行互相比较时，如果是升序，获取到 record[cur1] >= record[cur2] 时，由于是有序，所以 cur2 往后都是小于 cur1 对应的数的，所以能直接得到很多对逆序数。用降序也是同理

代码实现：

class Solution {
    vector<int> tmp;
public:
    int reversePairs(vector<int>& record) {
        tmp.resize(50010);
        return mergeSort(record, 0, record.size() - 1);
    }

    int mergeSort(vector<int>& record, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int ret = 0;
        int mid = left + ((right - left) >> 1);
        ret += mergeSort(record, left, mid);
        ret += mergeSort(record, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (record[cur1] <= record[cur2]) {
                tmp[i++] = record[cur1++];
            } else {
                ret += mid - cur1 + 1;
                tmp[i++] = record[cur2++];
            }
        }
        while (cur1 <= mid) {
            tmp[i++] = record[cur1++];
        }
        while (cur2 <= right) {
            tmp[i++] = record[cur2++];
        }
        for (int j = 0; j < right - left + 1; ++j) {
            record[j + left] = tmp[j];
        }
        return ret;
    }
};

4. 计算右侧小于当前元素的个数

题目描述：

示例：

计算右侧小于当前元素的个数

题解：

这题和上一题思路基本一致，唯一的难点就是要额外创建一个数组进行值和下表的绑定，因为题目要求的是返回每个 index 对应的值。有人就问了为什么不能用哈希表，可以是可以但是有重复值的话会很麻烦，因此额外创建一个数组进行 index 和值的绑定更方便，index 数组跟着 nums 数组移动就行

代码实现：

class Solution {
    vector<int> ret;
    vector<int> index;
    int tmpNums[500010];
    int tmpindex[500010];
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n, 0);
        index.resize(n);
        for (int i = 0; i < n; ++i) {
            index[i] = i;
        }
        mergeSort(nums, 0, n - 1);
        return ret;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tmpNums[i] = nums[cur2];
                tmpindex[i++] = index[cur2++];
            } else {
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpindex[i++] = index[cur1++];
            }
        }
        while (cur1 <= mid) {
            tmpNums[i] = nums[cur1];
            tmpindex[i++] = index[cur1++];
        }
        while (cur2 <= right) {
            tmpNums[i] = nums[cur2];
            tmpindex[i++] = index[cur2++];
        }
        for (int j = 0; j < right - left + 1; ++j) {
            nums[j + left] = tmpNums[j];
            index[j + left] = tmpindex[j];
        }
    }
};

5. 翻转对

题目描述：

示例：

翻转对

题解：

思路还是利用归并解决，但是要提前计算符合题目要求的翻转对，如果在排序过程中进行计算，会漏掉部分翻转对

细节问题：

(long long)nums[cur1] <= 2 * (long long)nums[cur2] 防止溢出

代码实现：

class Solution {
    vector<int> tmp;
    int ret = 0;
public:
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return ret;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur2 <= right) {
            while (cur1 <= mid && (long long)nums[cur1] <= 2 * (long long)nums[cur2]) {
                cur1++;
            }
            if (cur1 > mid) {
                break;
            }
            ret += mid - cur1 + 1;
            cur2++;
        }
        cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                tmp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= mid) {
            tmp[i++] = nums[cur1++];
        }
        while (cur2 <= right) {
            tmp[i++] = nums[cur2++];
        }
        for (int j = 0; j < right - left + 1; ++j) {
            nums[j + left] = tmp[j];
        }
    }
};