归并排序解决重要翻转对题目描述给定一个数组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(inti0;in;i){for(intji1;jn;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后面的所有数字都不大于当前数字。因此后面的所有数字也都满足条件可以一次性统计retright-cur21;如果当前条件不满足就让cur2向后移动尝试右区间中更小的数字。为什么使用降序排列本代码在归并时选择较大的数字if(nums[cur11]nums[cur22]){tmp[i]nums[cur11];}因此左右区间最终都是降序排列。在降序数组中左区间指针向后移动左边的数字变小右区间指针向后移动右边的数字也变小。当某个左边数字满足nums[cur1]2LL*nums[cur2]右区间从cur2到right的数字全部满足条件所以可以直接统计这一整段。完整代码classSolution{intret0;vectorinttmp;public:intmergeSort(vectorintnums,intleft,intright){if(leftright)return0;intmid(right-left)/2left;mergeSort(nums,left,mid);mergeSort(nums,mid1,right);// 统计跨越左右区间的重要翻转对intcur1left;intcur2mid1;while(cur1midcur2right){if(nums[cur1]2LL*nums[cur2]){retright-cur21;cur1;}else{cur2;}}// 合并两个降序区间intcur11left;intcur22mid1;inti0;while(cur11midcur22right){if(nums[cur11]nums[cur22]){tmp[i]nums[cur11];}else{tmp[i]nums[cur22];}}while(cur11mid){tmp[i]nums[cur11];}while(cur22right){tmp[i]nums[cur22];}// 将临时数组中的内容复制回原数组for(intuleft;uright;u){nums[u]tmp[u-left];}returnret;}intreversePairs(vectorintnums){ret0;intnnums.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)。归并排序的关键在于递归地将数组划分为左右两个区间保证左右区间有序利用有序性批量统计重要翻转对最后合并两个区间。本题的核心不是单纯排序而是利用排序后的区间关系减少不必要的逐个比较。