题解 | 数组中的逆序对

1、解题思路

1. 归并排序：归并排序的过程中，可以统计逆序对的数量。在合并两个已排序的子数组时，如果左侧的元素大于右侧的元素，则左侧剩余的所有元素都与该右侧元素构成逆序对。
2. 分治策略：将数组不断分成两半，递归处理。在合并时，计算跨子数组的逆序对数量。
3. 取模处理：在统计逆序对时，直接对结果进行 mod 1000000007 处理，防止溢出。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
        // write code here
        if (nums.empty()) {
            return 0;
        }
        vector<int> tmp(nums.size());
        return mergeSort(nums, tmp, 0, nums.size() - 1);
    }

  private:
    const int MOD = 1000000007;

    int mergeSort(vector<int>& nums, vector<int>& tmp, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int count = (mergeSort(nums, tmp, left, mid) + mergeSort(nums, tmp, mid + 1, right)) % MOD;
        count = (count + merge(nums, tmp, left, mid, right)) % MOD;
        return count;
    }

    int merge(vector<int>& nums, vector<int>& tmp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;
        int count = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
                count = (count + mid - i + 1) % MOD;
            }
        }
        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 count;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        // write code here
        if (nums == null || nums.length == 0) return 0;
        int[] tmp = new int[nums.length];
        return mergeSort(nums, tmp, 0, nums.length - 1);
    }

    private static final int MOD = 1000000007;

    private int mergeSort(int[] nums, int[] tmp, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int count = (mergeSort(nums, tmp, left, mid) + mergeSort(nums, tmp, mid + 1, right)) % MOD;
        count = (count + merge(nums, tmp, left, mid, right)) % MOD;
        return count;
    }

    private int merge(int[] nums, int[] tmp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;
        int count = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
                count = (count + mid - i + 1) % MOD;
            }
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= right) tmp[k++] = nums[j++];
        for (int idx = left; idx <= right; ++idx) nums[idx] = tmp[idx];
        return count;
    }
}

3、复杂度分析

• 时间复杂度：O(n log n)，归并排序的时间复杂度。
• 空间复杂度：O(n)，用于临时存储合并后的数组。