一、题目解析
1、i2*nums[j]，(i，j)记作一个翻转对
2、nums长度不会超过50000
3、nums中所有元素都在32位整数范围内
二、算法原理
解法1：暴力枚举 O(N^2)
固定一个数，枚举另一个数
解法2：分治 O(N*logN)
计算翻转对 (利用单调性，使用同向双指针)
方法1：计算当前元素后面，有多少元素的两倍比我小(降序)
由于降序，nums[cur1]>nums[cur2]*2，即nums[cur1]比cur2后面的所有数大，所以cur2~right的个数为right-cur2+1
方法2：计算当前元素之前，有多少元素的一般比我大(升序)
除2.0为了避免除不尽的情况，由于升序，nums[cur1]/2.0>nums[cur2]，nums[cur2]比cur1后面的所有数小，所以cur1~mid的个数为mid-cur1+1
合并两个有序数组
在升序中，tmp[i++] = nums[cur1]<=nums[cur2] ? nums[cur1++] : nums[cur2++]
在降序中，tmp[i++] = nums[cur1]<=nums[cur2] ? nums[cur2++] : nums[cur1++]
三、代码示例
解法2：降序
int tmp[50005];public: //降序 int reversePairs(vector& nums) { return mergeSort(nums,0,nums.size()-1); } int mergeSort(vector& nums,int left,int right) { int ret = 0; if(left>=right) return 0; int mid = (left+right)>>1; ret += mergeSort(nums,left,mid); ret += mergeSort(nums,mid+1,right); //统计翻转对 int cur1 = left,cur2 = mid+1; while(cur1<=mid) { while(cur2<=right && nums[cur1]/2.0 right) break; ret += right-cur2+1; cur1++; } int curr1 = left,curr2 = mid+1,i = 0; while(curr1<=mid && curr2<=right) tmp[i++] = nums[curr1]<=nums[curr2] ? nums[curr2++] : nums[curr1++]; //处理未遍历完 while(curr1<=mid) tmp[i++] = nums[curr1++]; while(curr2<=right) tmp[i++] = nums[curr2++]; //还原 for(int i = left;i<=right;i++) nums[i] = tmp[i-left]; return ret; }
这里不是nums[cur2]*2原因是，虽然都是32位整数范围内，但是*2可能会导致积超过32位的范围，所以/2.0
解法2：升序
int tmp[50005];public://升序 int reversePairs(vector& nums) { return mergeSort(nums,0,nums.size()-1); } int mergeSort(vector& nums,int left,int right) { int ret = 0; if(left>=right) return 0; int mid = (left+right)>>1; ret += mergeSort(nums,left,mid); ret += mergeSort(nums,mid+1,right); //统计翻转对 int cur1 = left,cur2 = mid+1; while(cur2<=right) { while(cur1<=mid && nums[cur1]/2.0 mid) break; ret += mid-cur1+1; cur2++; } int curr1 = left,curr2 = mid+1,i = 0; while(curr1<=mid && curr2<=right) tmp[i++] = nums[curr1]<=nums[curr2] ? nums[curr1++] : nums[curr2++]; //处理未遍历完 while(curr1<=mid) tmp[i++] = nums[curr1++]; while(curr2<=right) tmp[i++] = nums[curr2++]; //还原 for(int i = left;i<=right;i++) nums[i] = tmp[i-left]; return ret; }
看到最后，如果对您有所帮助，还请点赞、收藏和关注，我们下期再见！
