剑指 Offer 51. 数组中的逆序对 发表于 2022-07-31 123456789101112131415161718192021222324252627282930313233343536class 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. 数组中的逆序对