后端开发刷题 | 数组中的逆序对
描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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]
返回值：
7
示例2
输入：
[1,2,3]
返回值：
0
思路分析：
利用归并排序（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。
- 如果
- 重复上述过程，直到一个子数组的所有元素都被放入临时数组。
- 将另一个子数组中剩余的元素（如果有的话）直接复制到临时数组的末尾。
- 返回结果：
- 在合并过程中，累加跨越分割点的逆序对数量。
- 当整个数组被合并成一个有序数组时，返回累计的逆序对数量（取模以防止溢出）。
图例：
代码：
import java.util.*;
public class Solution {
int mod = 1000000007;
public int mergeSort(int left, int right, int[] data, int[] temp) {
//如果 left 大于等于 right，表示没有元素或只有一个元素，无需排序和计算逆序对，直接返回 0
if (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);
}
}