1.题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围: 对于 50%50% 的数据, 𝑠𝑖𝑧𝑒≤104size≤104
对于 100%100% 的数据, 𝑠𝑖𝑧𝑒≤105size≤105数组中所有数字的值满足 0≤𝑣𝑎𝑙≤1090≤val≤109
要求:空间复杂度 𝑂(𝑛)O(n),时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)O(nlogn)
输入描述:
题目保证输入的数组中没有的相同的数字
示例1
输入:
[1,2,3,4,5,6,7,0]返回值:
7示例2
输入:
[1,2,3]返回值:
0
2.解题思路
- 常规思路就是使用O(n^2)的时间复杂度暴力遍历这个数组,枚举每一对组合,统计所有的逆序对个数,需要对这个思路进行优化。
- 基于分治的思想,可以使用归并排序来解决这一题。归并排序时,每一次都会基于中心点mid,将数组拆分成leftNums和rightNums两个部分,直到leftNums和rightNums为长度等于1的子数组时,就能保证子数组是有序的,然后就需要对这两个有序的子数组进行融合,在融合时,我们可以发现如果当前rightNums[j] < leftNums[i],那么leftNums i下标及往后的所有元素都会和rightNums[j]形成一个逆序对,所以直接统计count += leftNums.length - i;这样就避免了内层的for循环
3.代码实现
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
private int count = 0;
public int InversePairs (int[] nums) {
// write code here
sort(nums);
return count;
}
//归并排序
public int[] sort(int[] nums) {
int n = nums.length;
if (n == 1) return nums;
int mid = n / 2;
int[] leftNums = sort(Arrays.copyOfRange(nums,0,mid));
int[] rightNums = sort(Arrays.copyOfRange(nums,mid,n));
return merge(leftNums,rightNums);
}
public int[] merge(int[] leftNums,int[] rightNums) {
int m = leftNums.length, n = rightNums.length;
int[] result = new int[m+n];
int i = 0, j = 0, p = 0;
while (i < m && j < n) {
if (leftNums[i] < rightNums[j]) {
result[p++] = leftNums[i++];
} else {
//统计逆序对
count += (m - i);
count %= 1000000007;
result[p++] = rightNums[j++];
}
}
while (i < m) {
result[p++] = leftNums[i++];
}
while (j < n) {
result[p++] = rightNums[j++];
}
return result;
}
}