后端开发刷题 | 数组中的逆序对

描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P mod 1000000007
数据范围：对于 50%50% 的数据, size≤104
对于 100%100% 的数据, size≤105

数组中所有数字的值满足 0≤val≤109

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

输入描述：

题目保证输入的数组中没有的相同的数字

示例1

输入：

[1,2,3,4,5,6,7,0]

返回值：

示例2

输入：

[1,2,3]

返回值：

思路分析：

利用归并排序（Merge Sort）的分治思想，在归并排序的合并过程中计算逆序对的数量。归并排序将数组分成两半，递归地对这两半进行排序，然后将排序好的两半合并成一个有序数组。在这个过程中，我们可以统计跨越分割点的逆序对数量。

详细步骤

分解：
- 如果数组只有一个元素或为空，则不需要排序，也没有逆序对，直接返回。
- 否则，找到数组的中间位置，将数组分成左右两个子数组。
- 递归地对左子数组和右子数组进行分解和排序，并计算它们各自的逆序对数量（这些逆序对不会跨越两个子数组之间的分割点）。
合并与计算逆序对：
- 创建一个临时数组用于合并两个已排序的子数组。
- 初始化三个指针：i 指向左子数组的起始位置，j 指向右子数组的起始位置，k 指向临时数组的起始位置。
- 遍历两个子数组，比较 left[i] 和 right[j] 的大小：
  - 如果 left[i] <= right[j]，说明 left[i] 及其之前的所有元素都不会与 right[j] 及其之后的元素形成逆序对，因此可以安全地将 left[i] 放入临时数组，并递增 i 和 k。
  - 如果 left[i] > right[j]，则说明 left[i] 与 right[j] 到 right[rightEnd]（右子数组的末尾）之间的所有元素都形成了逆序对。因此，将逆序对数量增加 rightEnd - j + 1（右子数组中剩余的元素数量），并将 right[j] 放入临时数组，递增 j 和 k。
- 重复上述过程，直到一个子数组的所有元素都被放入临时数组。
- 将另一个子数组中剩余的元素（如果有的话）直接复制到临时数组的末尾。
返回结果：
- 在合并过程中，累加跨越分割点的逆序对数量。
- 当整个数组被合并成一个有序数组时，返回累计的逆序对数量（取模以防止溢出）。

图例：

代码：

java">import java.util.*;public class Solution {int mod = 1000000007;public int mergeSort(int left, int right, int[] data, int[] temp) {//如果 left 大于等于 right，表示没有元素或只有一个元素，无需排序和计算逆序对，直接返回 0if (left >= right) {return 0;}int mid = (left + right) / 2;//递归地对左半部分和右半部分进行排序并计算逆序对数量，将结果相加并取模。int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data,temp);res %= mod;int i = left, j = mid + 1;//使用临时数组 temp 来辅助合并两个已排序的部分，并在合并过程中计算逆序对。for (int k = left; k <= right; k++) {temp[k] = data[k];}for (int k = left; k <= right; k++) {//当左边已经遍历完（i == mid +1），直接将右边剩余的元素复制到 data 中。if (i == mid + 1) {data[k] = temp[j++];} else if (j == right + 1 || temp[i] <= temp[j]) {//如果右边已经遍历完或左边当前元素小于等于右边当前元素，将左边当前元素复制到data 中。data[k] = temp[i++];} else {//如果左边当前元素大于右边当前元素，则将右边当前元素复制到//data 中，并增加逆序对计数（因为左边剩余的所有元素（mid -i + 1）都大于右边当前元素，形成逆序对）。data[k] = temp[j++];res += mid - i + 1;}}return res%mod;}/*** @param nums int整型一维数组* @return int整型*/public int InversePairs (int[] nums) {int n=nums.length;int[] res=new int[n];return mergeSort(0,n-1,nums,res);}
}