hard.归并排序.剑指offer. 逆序对

数组中的逆序对可以通过归并排序的方法在O(n log n)的时间复杂度内高效求解。

• 问题理解：逆序对指的是数组中前面元素大于后面元素的对数。例如，数组[7,5,6,4]的逆序对为(7,5)、(7,6)、(7,4)、(5,4)、(6,4)，总数为5。

• 暴力解法：

  算法思想：双重循环遍历数组，外层循环固定一个元素，内层循环遍历其后的所有元素，统计满足逆序对条件的对数。

  时间复杂度：O(n2)，适用于小规模数据，但效率较低。

  Java实现：

  public int reversePairs1(int[] nums) { if (nums == null || nums.length < 2) return 0; int count = 0; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] > nums[j]) count++; } } return count;}

• 归并排序解法：

  算法思想：

  分治策略：将数组递归拆分为单个元素，然后逐步合并。

  合并时统计逆序对：在合并两个有序子数组时，若右子数组的元素小于左子数组的元素，则左子数组中剩余元素均能与该右元素构成逆序对，数量为mid - i + 1（mid为左子数组末尾索引，i为当前左子数组比较索引）。

  时间复杂度：O(n log n)，显著优于暴力解法。

  关键步骤：

  递归拆分：将数组拆分为左右两部分，分别递归处理。

  合并与统计：合并时比较左右子数组元素，统计逆序对并生成有序数组。

  Java实现：

  class Solution { public int reversePairs(int[] nums) { if (nums == null || nums.length < 2) return 0; int[] copy = new int[nums.length]; for (int i = 0; i < nums.length; i++) copy[i] = nums[i]; int[] tmp = new int[nums.length]; return reversePairs(copy, 0, nums.length - 1, tmp); } private int reversePairs(int[] nums, int left, int right, int[] tmp) { if (left >= right) return 0; int mid = (left + right) / 2; int leftPairs = reversePairs(nums, left, mid, tmp); int rightPairs = reversePairs(nums, mid + 1, right, tmp); int mergePairs = merge(nums, left, mid, right, tmp); return leftPairs + rightPairs + mergePairs; } private int merge(int[] nums, int left, int mid, int right, int[] tmp) { int tmpPos = left; int count = 0; int i = left, j = mid + 1; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) { tmp[tmpPos++] = nums[i++]; } else { tmp[tmpPos++] = nums[j++]; count += mid - i + 1; } } while (i <= mid) tmp[tmpPos++] = nums[i++]; while (j <= right) tmp[tmpPos++] = nums[j++]; for (tmpPos = left; tmpPos <= right; tmpPos++) nums[tmpPos] = tmp[tmpPos]; return count; }}

• 合并方法优化版本：

  改进点：在合并时直接使用原数组的临时存储，减少拷贝次数。

  Java实现：

  private int mergeAndCountReversePairs(int[] data, int left, int mid, int right, int[] tmp) { for (int i = left; i <= right; i++) tmp[i] = data[i]; int count = 0; int i = left, j = mid + 1; for (int k = left; k <= right; k++) { if (i == mid + 1) data[k] = tmp[j++]; else if (j == right + 1) data[k] = tmp[i++]; else if (tmp[i] <= tmp[j]) data[k] = tmp[i++]; else { data[k] = tmp[j++]; count += mid - i + 1; } } return count;}

总结：归并排序通过分治策略将问题分解为子问题，并在合并过程中高效统计逆序对，实现了时间复杂度的优化。其核心在于利用有序子数组的性质，快速计算逆序对数量，适用于大规模数据的高效处理。