【算法面试必刷Java版二十】数组中的逆序对
盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101
🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚
🚴🏻♂️个人主页：莫逸风
👨🏻💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻
🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发
题目：数组中的逆序对
描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围： 对于 50% 的数据, size≤104
对于 100% 的数据, size≤105
数组中所有数字的值满足0≤val≤1000000
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)
题目保证输入的数组中没有的相同的数字
思路：归并排序
归并排序遵循分治思想，先分后治。
- 划分阶段：将待划分区间从中点划分成两部分；
- 排序阶段：使用归并排序递归地处理子序列，同时统计逆序对；
- 合并阶段：将排好序的子序列合并，同时累加逆序对。
代码：
public int InversePairs(int [] array) {
int n = array.length;
int[] res = new int[n];
return mergeSort(0, n - 1, array, res);
}
public int mod = 1000000007;
public int mergeSort(int left, int right, int [] data, int [] temp){
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;
for (int k = left; k <= right; k++)
temp[k] = data[k];
for (int k = left; k <= right; k++) {
if (i == mid + 1)
data[k] = temp[j++];
else if (j == right + 1 || temp[i] <= temp[j])
data[k] = temp[i++];
else { //左边比右边大，答案增加
data[k] = temp[j++];
res += mid - i + 1; // 统计逆序对
}
}
return res % mod;
}
推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101