AcWing 65. 数组中的逆序对
原题链接
困难
作者:
不哭死神
,
2021-09-03 17:53:21
,
所有人可见
,
阅读 255
利用归并排序来计算
class Solution {
private static int res = 0;
public int inversePairs(int[] nums) {
if (nums == null || nums.length == 0) return 0;
merge_sort(nums, 0, nums.length - 1);
return res;
}
private void merge_sort(int[] nums, int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(nums, l, mid);
merge_sort(nums, mid + 1, r);
int i = l, j = mid + 1, k = 0;
int[] tmp = new int[r - l + 1];
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
else {
tmp[k++] = nums[j++];
res += mid - i + 1;
}
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
}
}