企业官网建设流程全解析

归并排序解决重要翻转对

题目描述

给定一个数组nums，如果满足：

i < j 且 nums[i] > 2 * nums[j]

那么(i, j)就是一对重要翻转对。

请返回数组中重要翻转对的数量。

例如：

输入：[1,3,2,3,1] 输出：2

满足条件的下标对为：

(1, 4)：3 > 2 * 1 (3, 4)：3 > 2 * 1

小记:今天这题的hard难题和前几天类似,但是没有了下标这种比较难操作的元素,只需要我在比较完二倍大小后再重新归并排序,简单了很多,今天过的也很充实,还不错

基本思路

最直接的方法是枚举所有下标对：

for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){if(nums[i]>2*nums[j])ret++;}}

这种方法的时间复杂度是O(N^2)。

当数组长度达到50000时，效率无法接受。

这道题可以使用归并排序，将数组分成左右两个有序区间，然后统计跨越左右区间的重要翻转对。

核心思想是：

利用归并排序，把逐个比较转化为按段统计。

归并过程中的统计

假设左右两个区间已经按照降序排列：

左区间：[10, 6, 3] 右区间：[4, 2, 1]

对于左区间中的某个数字nums[cur1]，从右区间的cur2开始判断。

如果：

nums[cur1]>2LL*nums[cur2]

由于右区间是降序排列的，所以cur2后面的所有数字都不大于当前数字。

因此，后面的所有数字也都满足条件，可以一次性统计：

ret+=right-cur2+1;

如果当前条件不满足，就让cur2向后移动，尝试右区间中更小的数字。

为什么使用降序排列

本代码在归并时选择较大的数字：

if(nums[cur11]>nums[cur22]){tmp[i++]=nums[cur11++];}

因此左右区间最终都是降序排列。

在降序数组中：

• 左区间指针向后移动，左边的数字变小；
• 右区间指针向后移动，右边的数字也变小。

当某个左边数字满足：

nums[cur1]>2LL*nums[cur2]

右区间从cur2到right的数字全部满足条件，所以可以直接统计这一整段。

完整代码

classSolution{intret=0;vector<int>tmp;public:intmergeSort(vector<int>&nums,intleft,intright){if(left>=right)return0;intmid=(right-left)/2+left;mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);// 统计跨越左右区间的重要翻转对intcur1=left;intcur2=mid+1;while(cur1<=mid&&cur2<=right){if(nums[cur1]>2LL*nums[cur2]){ret+=right-cur2+1;cur1++;}else{cur2++;}}// 合并两个降序区间intcur11=left;intcur22=mid+1;inti=0;while(cur11<=mid&&cur22<=right){if(nums[cur11]>nums[cur22]){tmp[i++]=nums[cur11++];}else{tmp[i++]=nums[cur22++];}}while(cur11<=mid){tmp[i++]=nums[cur11++];}while(cur22<=right){tmp[i++]=nums[cur22++];}// 将临时数组中的内容复制回原数组for(intu=left;u<=right;u++){nums[u]=tmp[u-left];}returnret;}intreversePairs(vector<int>&nums){ret=0;intn=nums.size();tmp.resize(n);returnmergeSort(nums,0,n-1);}};

代码中的关键细节

1. 使用2LL防止溢出

题目中的数字可能达到 32 位整数范围。

如果直接写：

nums[cur1]>2*nums[cur2]

那么乘法可能在int范围内发生溢出。

因此写成：

nums[cur1]>2LL*nums[cur2]

让运算转换为long long类型，更安全。

2. 统计和归并使用不同的指针

统计重要翻转对时使用：

cur1、cur2

真正归并时使用：

cur11、cur22

这是因为统计过程会移动指针，但不能影响后面的正常归并。

3. 必须先统计，再归并

递归完成后，左右区间已经有序。

此时先统计跨区间的重要翻转对，再将两个区间合并。

如果先合并，就会破坏原来的左右区间边界，导致统计逻辑混乱。

复杂度分析

归并排序会将数组不断二分，并在每一层进行线性合并。

因此：

时间复杂度：O(N log N) 空间复杂度：O(N)

其中O(N)的额外空间主要来自临时数组tmp。

总结

这道题不能直接使用普通的两重循环，否则时间复杂度为O(N^2)。

归并排序的关键在于：

1. 递归地将数组划分为左右两个区间；
2. 保证左右区间有序；
3. 利用有序性批量统计重要翻转对；
4. 最后合并两个区间。

本题的核心不是单纯排序，而是利用排序后的区间关系，减少不必要的逐个比较。