在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4] 输出: 5
两区间及跨区间
class Solution {
public int reversePairs(int [] array) {
int len = array.length;
if(len < 2)
return 0;
// 归并排序
int[] temp = new int[len];
return mergeSort(array, 0, len-1, temp);
}
// 归并排序
private static int mergeSort(int[] array, int left, int right, int[] temp) {
if(left >= right)
return 0;
int mid = left + (right - left) / 2; // 防止溢出
// [left, mid] [mid+1, right]
int leftPairs = mergeSort(array, left, mid, temp);
int rightPairs = mergeSort(array, mid+1, right, temp);
// 优化
if(array[mid] <= array[mid+1])
return leftPairs + rightPairs;
int crossPairs = mergeCrossSort(array, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
// 跨区间排序
private static int mergeCrossSort(int[] array, int left, int mid, int right, int[] temp) {
int count = 0;
for(int i = left; i <= right; i++) {
temp[i] = array[i];
}
// 边界的起始位置
int i = left;
int j = mid + 1;
for(int k = left; k <= right; k++) {
if(i == mid + 1) {
array[k] = temp[j];
j++;
}else if(j == right + 1) {
array[k] = temp[i];
i++;
}
else if(temp[i] <= temp[j]) { // 没有逆序对
array[k] = temp[i];
i++;
}else {
array[k] = temp[j];
j++;
count += mid - i + 1; // 左比右,因为递增满足的逆序对计数规律
}
}
return count;
}
}
private long cnt = 0;
private int[] tmp; // 在这里声明辅助数组,而不是在 merge() 递归函数中声明
public int InversePairs(int[] nums) {
tmp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1);
return (int) (cnt % 1000000007);
}
private void mergeSort(int[] nums, int l, int h) {
if (h - l < 1)
return;
int m = l + (h - l) / 2;
mergeSort(nums, l, m);
mergeSort(nums, m + 1, h);
merge(nums, l, m, h);
}
private void merge(int[] nums, int l, int m, int h) {
int i = l, j = m + 1, k = l;
while (i <= m || j <= h) {
if (i > m)
tmp[k] = nums[j++];
else if (j > h)
tmp[k] = nums[i++];
else if (nums[i] <= nums[j])
tmp[k] = nums[i++];
else {
tmp[k] = nums[j++];
this.cnt += m - i + 1; // nums[i] > nums[j],说明 nums[i...mid] 都大于 nums[j]
}
k++;
}
for (k = l; k <= h; k++)
nums[k] = tmp[k];
}