Poison

剑指 Offer 51. 数组中的逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public int reversePairs(int[] nums) {
int[] tmp = new int[nums.length];
return mergeSort(nums, tmp, 0, nums.length - 1);
}

private int mergeSort(int[] nums, int[] tmp, int left, int right) {
if (left >= right) {
return 0;
}

int mid = (left + right) >>> 1;
int res = mergeSort(nums, tmp, left, mid) + mergeSort(nums, tmp, mid + 1, right);

System.arraycopy(nums, left, tmp, left, right - left + 1);

int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
if (i > mid) {
nums[k] = tmp[j++];
} else if (j > right) {
nums[k] = tmp[i++];
} else if (tmp[i] <= tmp[j]) {
nums[k] = tmp[i++];
} else {
// 此时 tmp[i] > tmp[j], 我们统计大于 tmp[j] 的元素个数
// 因为左侧数组已经有序,所以左侧数组中大于等于 tmp[i] 的元素个数即为逆序对的个数
// 因为即将执行 j++, 所以保证了每个 tmp[j] 相关的逆序对只被统计一次
res += mid - i + 1;
nums[k] = tmp[j++];
}
}

return res;
}
}
Reference

剑指 Offer 51. 数组中的逆序对