归并排序解决LeetCode翻转对问题

1. 问题背景与核心挑战LeetCode 493题翻转对Reverse Pairs是算法练习中的一道经典难题要求统计数组中满足i j且nums[i] 2*nums[j]的元素对数。这个问题看似简单但直接使用双重循环的暴力解法时间复杂度为O(n²)在数据量较大时如10^5级别会超时。我在实际刷题和面试准备过程中发现这道题考察的核心是分治思想与归并排序的灵活运用。相比单纯的排序问题它需要我们在归并过程中同步完成特定条件的统计这对理解算法本质提出了更高要求。2. 解法思路与技术选型2.1 暴力解法的局限性最直观的解法是两层循环遍历所有(i,j)组合int count 0; for(int i0; inums.length; i){ for(int ji1; jnums.length; j){ if(nums[i] 2L*nums[j]) count; } } return count;当n5×10^4时操作次数将达到25亿次远超一般OJ系统1秒内能处理的10^8次操作限制。2.2 分治与归并排序的优势归并排序天然具有分治特性将数组分成两半分别处理分治合并两个有序子数组时进行特定统计时间复杂度优化到O(n log n)关键突破点在于在合并两个有序子数组前可以高效统计跨子数组的翻转对数量。因为左右子数组已经各自有序可以利用这个性质通过双指针技巧在O(n)时间内完成统计。3. 归并排序解法实现细节3.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) mergeSort(nums, mid1, right); count merge(nums, left, mid, right); return count; }3.2 关键统计逻辑实现private int merge(int[] nums, int left, int mid, int right){ // 统计翻转对 int i left, j mid1; int count 0; while(i mid j right){ if(nums[i] 2L * nums[j]){ count mid - i 1; j; }else{ i; } } // 标准归并排序合并过程 int[] temp new int[right-left1]; // ...省略合并代码... return count; }注意必须使用2L强制转换为long类型避免大数相乘导致的整数溢出问题。这是实际编码中常见的坑点。4. 树状数组解法对比分析4.1 离散化处理由于原始数值范围可能很大如[-2^31, 2^31-1]需要先对数组进行离散化收集所有nums[i]和2*nums[i]1确保严格大于排序后去重建立值到排名的映射4.2 树状数组操作// 离散化后的实现 public int reversePairs(int[] nums) { // 离散化代码省略... BIT bit new BIT(discretized.size()); int res 0; for(int inums.length-1; i0; i--){ int val discretized.get(nums[i]); res bit.query(lowerBound(discretized, 2L*nums[i]1)); bit.update(val, 1); } return res; }4.3 性能对比方法时间复杂度空间复杂度编码复杂度归并排序O(n log n)O(n)中等树状数组O(n log n)O(n)较高暴力解法O(n²)O(1)简单归并排序版本在实际面试中更受青睐因为不需要处理离散化的边缘情况代码结构更清晰直观空间使用更可控5. 常见错误与调试技巧5.1 整数溢出问题错误示例if(nums[i] 2 * nums[j]) // 当nums[j]1e9时会溢出正确写法if(nums[i] 2L * nums[j]) // 使用long类型5.2 统计时机错误必须在合并两个有序数组前完成统计如果在合并后才统计会漏掉跨子数组的翻转对。5.3 边界条件处理测试用例应包括空数组全相同元素数组最大/最小整数值完全正序/逆序数组6. 算法扩展与变种6.1 CDQ分治解法CDQ分治是处理三维偏序问题的利器虽然本题是二维偏序但可以用其思想将每个元素视为(i, nums[i])的二元组第一维按i排序天然满足ij第二维用归并处理nums[i]2*nums[j]6.2 实际工程应用类似算法可用于金融交易系统中的异常交易检测基因组序列比对中的反转位点统计版本控制系统中的代码变更影响分析7. 性能优化实践7.1 归并排序的空间优化可以复用临时数组而非每次新建// 类成员变量 private int[] temp; // 初始化时分配一次 temp new int[nums.length];7.2 提前终止优化当左子数组最小值已经2*右子数组最大值时所有左子数组元素都满足条件if(nums[left] 2L * nums[right]){ count (mid-left1)*(right-mid); // 快速合并剩余元素... }8. 不同语言实现要点8.1 C实现注意使用vector代替原生数组更安全注意iterator的使用范围int mergeSort(vectorint nums, int left, int right){ if(left right) return 0; int mid left (right-left)/2; int count mergeSort(nums, left, mid) mergeSort(nums, mid1, right); // 统计逻辑 int i left, j mid1; while(i mid j right){ if(nums[i] 2LL * nums[j]){ count mid - i 1; j; }else{ i; } } // ...合并逻辑 return count; }8.2 Python实现特点利用切片简化代码注意整数自动转为long的特性def reversePairs(nums): def merge_sort(l, r): if l r: return 0 mid (l r) // 2 count merge_sort(l, mid) merge_sort(mid1, r) # 统计逻辑 j mid 1 for i in range(l, mid1): while j r and nums[i] 2 * nums[j]: j 1 count j - (mid 1) # 合并 nums[l:r1] sorted(nums[l:r1]) return count return merge_sort(0, len(nums)-1)9. 测试用例设计策略完整的测试应包含以下场景常规测试Input: [1,3,2,3,1] Output: 2边界测试Input: [2147483647,2147483647,2147483647] // MAX_INT Output: 0性能测试Input: [10000000,9999999,...,1] // 1e5个逆序元素 Expected: 在1秒内完成特殊值测试Input: [] // 空数组 Output: 010. 实际编码中的经验总结调试技巧在归并过程中打印子数组状态可视化统计过程System.out.printf(Processing [%d,%d] and [%d,%d]\n, left, mid, mid1, right);性能分析使用JMH进行微基准测试比较不同实现的吞吐量Benchmark public void testMergeSortSolution(Blackhole bh) { bh.consume(solution.reversePairs(testData)); }代码风格将统计逻辑与合并逻辑分离提高可读性private int countPairs(int[] nums, int left, int mid, int right){ // 纯统计逻辑 } private void merge(int[] nums, int left, int mid, int right){ // 纯合并逻辑 }扩展思考如果条件改为nums[i] 3*nums[j]算法结构是否变化实际上只需要修改比较条件整体框架保持不变。