题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。例如，在数组 {7, 5, 6, 4} 中，一共存在 5 个逆序对，分别是 (7, 6)、(7, 5)、(7, 4)、(6, 4) 和 (5, 4)。
练习地址
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
参考答案
class Solution {
public int reversePairs(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] copy = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
copy[i] = nums[i];
}
return inverse(nums, copy, 0, nums.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;
} else {
copy[copyIndex--] = array[rightIndex--];
}
}
while (leftIndex >= start) {
copy[copyIndex--] = array[leftIndex--];
}
while (rightIndex > mid) {
copy[copyIndex--] = array[rightIndex--];
}
return left + right + count;
}
}
复杂度分析
- 时间复杂度：O(nlogn)。
- 空间复杂度：O(n)。
