题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1：
输入: [7,5,6,4]
输出: 5
参考答案：
class Solution {
public int reversePairs(int[] nums) {
int length = nums.length;
// 少于2个元素直接返回0，不存在逆序对
if (length < 2) {
return 0;
}
int[] temp = new int[length];
int ans = reversePairs(nums, 0, length-1, temp);
// System.out.println(Arrays.toString(nums));
return ans;
}
/**
* nums[left..right] 计算有序数组里的逆序对个数
**/
public int reversePairs(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
// 不用(left + right)/2，防止整型溢出
int mid = left + (right - left) / 2;
int leftCount = reversePairs(nums, left, mid, temp);
int rightCount = reversePairs(nums, mid+1, right, temp);
// 已经是有序数组，直接返回两个数组的逆序对
if (nums[mid] < nums[mid+1]) {
return leftCount + rightCount;
}
int crossCount = mergeAndCount(nums, left, mid, right, temp);
return leftCount + rightCount + crossCount;
}
public int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
// temp是辅助数组
for (int i=left; i<=right; i++) {
temp[i] = nums[i];
}
int i = left;
int j = mid + 1;
int count = 0;
// 合并temp[i..mid]和temp[mid..right]数组到nums[left..right]
for (int k=left; k<=right; k++) {
if (i == mid + 1) {
nums[k] = temp[j];
j++;
}
else if (j == right + 1) {
nums[k] = temp[i];
i++;
}
else if (temp[i] <= temp[j]) {
nums[k] = temp[i];
i++;
}
else if (temp[i] > temp[j]) {
nums[k] = temp[j];
j++;
// 第二个区间小于第一区间，逆序对个数等于第一区间剩下的元素个数
count += (mid - i + 1);
}
}
return count;
}
}
执行用时：34 ms
思路
采用归并排序算法的思路，归并两个有序数组时，当需要归并右边的数组时，这时候它的逆序对个数等于左边数组待归并的数量，再加上左右两个数组的逆序对数量，就是最终结果。按照分治思想，左右两个数组的逆序对可以用同样的算法求得。