题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出,即输出P%1000000007。例如,在数组{7, 5, 6, 4}中,一共存在5个逆序对,分别是(7, 6)、(7, 5)、(7, 4)、(6, 4)和(5, 4)。
练习地址
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
参考答案
public class Solution {
public int InversePairs(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int[] copy = new int[array.length];
for (int i = 0; i < array.length; i++) {
copy[i] = array[i];
}
return inverse(array, copy, 0, array.length - 1);
}
private int inverse(int[] array, int[] copy, int start, int end) {
if (start == end) {
return 0;
}
int mid = (start + end) / 2;
int left = inverse(copy, array, start, mid);
int right = inverse(copy, array, mid + 1, end);
int leftIndex = mid, rightIndex = end, copyIndex = end, count = 0;
while (leftIndex >= start && rightIndex > mid) {
if (array[leftIndex] > array[rightIndex]) {
copy[copyIndex--] = array[leftIndex--];
count += rightIndex - mid;
if (count >= 1000000007) {
count %= 1000000007;
}
} else {
copy[copyIndex--] = array[rightIndex--];
}
}
while (leftIndex >= start) {
copy[copyIndex--] = array[leftIndex--];
}
while (rightIndex > mid) {
copy[copyIndex--] = array[rightIndex--];
}
return (left + right + count) % 1000000007;
}
}
复杂度分析
- 时间复杂度:O(nlogn)。
- 空间复杂度:O(n)。
网友评论