剑指51：数组中的逆序对

传送门

nowcoder
leetcode

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求出这个数组中的逆序对的总数P。
将 P 对 1000000007 取模的结果输出。

C++ 代码 - nowcoder

/*
    递归实现，归并排序：从前向后归并

    先把数组分割为子数组，统计出子数组内部逆序对的个数，
    再统计出两个相邻子数组之间的逆序对的个数。
*/
class Solution {
public:
    const int MOD = 1000000007;

    int InversePairs(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> copy(nums); // 辅助数组，每次递归后有序
        return InversePairsCore(nums, copy, 0, nums.size() - 1);
    }

    int InversePairsCore(vector<int>& nums, vector<int>& copy, int begin, int end) {
        if (begin == end) return 0;

        int mid = begin + (end - begin) / 2;
        int left = InversePairsCore(copy, nums, begin, mid);
        int right = InversePairsCore(copy, nums, mid + 1, end);

        int end1 = mid; // 比较从尾端开始
        int end2 = end; // 比较从尾端开始
        int copyIndex = end; // 比较结果存入辅助数组尾端
        long res = 0;
        // 归并排序：两个有序数组合成一个有序表（从尾端开始是为了计数）
        while (begin <= end1 && mid + 1 <= end2) {
            if (nums[end1] > nums[end2]) {
                copy[copyIndex --] = nums[end1 --];
                res += end2 - mid;
                res %= MOD;
            } else {
                copy[copyIndex --] = nums[end2 --];
            }
        }
        while (begin <= end1) copy[copyIndex --] = nums[end1 --];
        while (mid + 1 <= end2) copy[copyIndex --] = nums[end2 --];

        return (left + right + res) % MOD;
    }
};

/*
    非递归实现，归并排序：从前向后归并
*/
class Solution {
public:
    const int MOD = 1000000007;

    int InversePairs(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> copy(nums); // 辅助数组，每次递归后有序
        return InversePairsCore(nums, copy, 0, nums.size() - 1);
    }

    int InversePairsCore(vector<int>& nums, vector<int>& copy, int begin, int end) {
        if (begin == end) return 0;

        int mid = begin + (end - begin) / 2;
        int low1 = begin, high1 = mid, low2 = mid + 1, high2 = end;
        int left = InversePairsCore(copy, nums, low1, high1); // 这一步，减少了数据交换的这一步
        int right = InversePairsCore(copy, nums, low2, high2);

        long res = 0;
        int copyIndex = low1;
        // 归并排序：两个有序数组合成一个有序表。两两进行比较，若前面的数大于后面的数，则构成逆序对。
        while (low1 <= high1 && low2 <= high2) {
            if (nums[low1] < nums[low2]) {
                copy[copyIndex ++] = nums[low1 ++];
            } else {
                copy[copyIndex ++] = nums[low2 ++];
                res += high1 - low1 + 1;
                res %= MOD;
            }
        }
        while (low1 <= high1) copy[copyIndex ++] = nums[low1 ++];
        while (low2 <= high2) copy[copyIndex ++] = nums[low2 ++];

        return (left + right + res) % MOD;
    }
};

C++ 代码 - leetcode

class Solution {
private:
    vector<int> temp;
    int count = 0; // 记录「翻转对」的个数

public:
    int reversePairs(vector<int>& nums) {
        if (nums.size() == 0) return 0;

        temp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1); // 执行归并排序
        return count;
    }

    void mergeSort(vector<int>& nums, int low, int high) {
        if (low == high) {
            return;
        }

        int mid = low + (high - low) / 2;
        mergeSort(nums, low, mid);
        mergeSort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }

    void merge(vector<int>& nums, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            temp[i] = nums[i];
        }

        // 优化，维护左闭右开区间 [mid + 1, end) 中的元素乘 2 小于 nums[i]
        // end 是开区间，可以保证初始区间 [mid + 1, mid + 1) 是一个空区间
        int end = mid + 1;
        for (int i = low; i <= mid; i++) {
            // nums 中的元素可能较大，乘 2 可能溢出，所以转化成 long
            while (end <= high && nums[end] < nums[i]) {
                end ++;
            }
            count += end - (mid + 1);
        }

        // 双指针技巧，合并两个有序数组
        int i = low, j = mid + 1;
        for (int k = low; k <= high; k ++) {
            if (i == mid + 1) {
                nums[k] = temp[j ++];
            } else if (j == high + 1) {
                nums[k] = temp[i ++];
            } else if (temp[i] > temp[j]) {
                nums[k] = temp[j ++];
            } else {
                nums[k] = temp[i ++];
            }
        }
    }
};=