LeetCode 493翻转对 | 归并排序应用引言翻转对Reverse Pairs是 LeetCode 第 493 题难度为 Hard。题目要求在一个整数数组中统计满足条件 i j 且 nums[i] 2*nums[j] 的翻转对数量。这道题是归并排序的经典应用展示了如何在归并排序的过程中统计满足条件的元素对。这个问题可以用归并排序在 O(n log n) 时间内解决其核心思想是在归并过程中当左半部分的元素大于右半部分的元素时统计该元素与右半部分所有元素的翻转对。问题分析题目描述给定一个数组 nums返回翻转对的数量。翻转对定义为满足 i j 且 nums[i] 2*nums[j] 的索引对 (i, j)。例如输入 [1, 3, 2, 3, 1]返回 2因为(3, 2): 3 2*2 4? 不满足实际上正确的翻转对是 (2, 3) 和 (2, 4) 或类似问题特点这个问题的挑战在于如何在 O(n log n) 时间内解决而不是 O(n²) 的暴力方法。归并排序提供了一种巧妙的解决方案在归并排序的合并阶段利用左右两部分已经排序好的特性高效统计翻转对。解决方案暴力方法def reversePairs_brute(nums): count 0 n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] 2 * nums[j]: count 1 return count暴力方法的时间复杂度是 O(n²)对于大规模数据效率低下。归并排序方法def reversePairs(nums): if len(nums) 1: return 0 def merge_sort(nums, temp, left, right): if left right: return 0 mid (left right) // 2 count merge_sort(nums, temp, left, mid) count merge_sort(nums, temp, mid 1, right) i, j left, mid 1 while i mid: while j right and nums[i] 2 * nums[j]: j 1 count j - (mid 1) i 1 i, j, k left, mid 1, left while i mid and j right: if nums[i] nums[j]: temp[k] nums[i] i 1 else: temp[k] nums[j] j 1 k 1 while i mid: temp[k] nums[i] i 1 k 1 while j right: temp[k] nums[j] j 1 k 1 for i in range(left, right 1): nums[i] temp[i] return count return merge_sort(nums, [0] * len(nums), 0, len(nums) - 1)算法详解归并排序方法的核心在于合并阶段。当左右两部分都已排序时对于左半部分的每个元素 nums[i]我们需要在右半部分中找到第一个大于 2nums[i] 的元素的位置 j。由于右半部分已排序j 之后的所有元素都满足大于 2nums[i]因此翻转对的数量为 j - (mid 1)。为什么归并排序有效分割阶段归并排序首先将数组递归地分成两半直到每个子数组只有一个元素。这个分割过程本身不改变元素的相对位置。合并阶段在合并阶段左右两部分都已排序。我们遍历左半部分的每个元素使用双指针在右半部分中找到满足条件的元素数量。由于左右两部分都是已排序的我们可以使用两个指针 i 和 j 来遍历i 从 left 到 midj 从 mid1 到 right当 nums[i] 2*nums[j] 时由于 nums[j] 是右半部分中最小的未处理元素j 之后的所有元素也都满足条件因此可以一次性统计所有翻转对。计数后合并统计完翻转对后我们需要将左右两部分合并为有序数组以便后续的递归处理。复杂度分析时间复杂度时间复杂度为 O(n log n)。归并排序的递归深度是 log n每一层都需要 O(n) 时间处理合并和计数。空间复杂度空间复杂度为 O(n)用于存储临时数组 temp。代码实现Python 实现def reversePairs(nums): if len(nums) 1: return 0 def merge_sort(nums, temp, left, right): if left right: return 0 mid (left right) // 2 count merge_sort(nums, temp, left, mid) count merge_sort(nums, temp, mid 1, right) i, j left, mid 1 while i mid: while j right and nums[i] 2 * nums[j]: j 1 count j - (mid 1) i 1 i, j, k left, mid 1, left while i mid and j right: if nums[i] nums[j]: temp[k] nums[i] i 1 else: temp[k] nums[j] j 1 k 1 while i mid: temp[k] nums[i] i 1 k 1 while j right: temp[k] nums[j] j 1 k 1 for i in range(left, right 1): nums[i] temp[i] return count return merge_sort(nums, [0] * len(nums), 0, len(nums) - 1)Java 实现public int reversePairs(int[] nums) { return mergeSort(nums, 0, nums.length - 1); } private int mergeSort(int[] nums, int left, int right) { if (left right) { return 0; } int mid left (right - left) / 2; int count mergeSort(nums, left, mid); count mergeSort(nums, mid 1, right); int i left, j mid 1; while (i mid) { while (j right (long)nums[i] 2 * (long)nums[j]) { j; } count j - (mid 1); i; } int[] temp new int[right - left 1]; i left; j mid 1; int k 0; while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { temp[k] nums[j]; } } while (i mid) { temp[k] nums[i]; } while (j right) { temp[k] nums[j]; } System.arraycopy(temp, 0, nums, left, temp.length); return count; }边界情况处理空数组当数组为空或只有一个元素时没有翻转对返回 0。大整数注意 2*nums[j] 可能超出整数范围需要使用 long 类型进行计算。负数算法同样适用于包含负数的数组因为比较操作同样适用。测试用例def test_reverse_pairs(): assert reversePairs([1, 3, 2, 3, 1]) 3 assert reversePairs([2, 4, 1, 3, 5]) 3 assert reversePairs([1]) 0 assert reversePairs([]) 0 assert reversePairs([1, 2, 3, 4, 5]) 0 assert reversePairs([5, 4, 3, 2, 1]) 10 print(所有测试用例通过)扩展问题条件变为 nums[i] nums[j]如果问题变为统计普通的逆序对i j 且 nums[i] nums[j]算法需要稍作修改在合并阶段当 nums[i] nums[j] 时说明 nums[i] 大于右半部分的所有未处理元素计数应加上 (right - j 1)。条件变为 nums[i] k * nums[j]如果 k 是变量而不是固定的 2算法逻辑不变只需将比较条件从 nums[i] 2nums[j] 改为 nums[i] knums[j]。总结翻转对问题展示了归并排序在解决条件计数问题中的应用。通过在归并过程中利用已排序的特性我们可以在 O(n log n) 时间内统计满足条件的翻转对数量。这个问题的关键洞察是当左右两部分都已排序时对于左半部分的每个元素我们可以一次性找到右半部分中满足条件的元素数量避免了 O(n²) 的暴力方法。