分治-归并-493.翻转对-力扣(LeetCode)

一、题目解析

1、i<j且nums>2*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：降序

2. int tmp[50005];
3. public:
4.     //降序
5.     int reversePairs(vector<int>& nums)
6.     {
7.         return mergeSort(nums,0,nums.size()-1);
8.     }
9.     int mergeSort(vector<int>& nums,int left,int right)
10.     {
11.         int ret = 0;
12.         if(left>=right) return 0;
14.         int mid = (left+right)>>1;
15.         ret += mergeSort(nums,left,mid);
16.         ret += mergeSort(nums,mid+1,right);
17.         //统计翻转对
18.         int cur1 = left,cur2 = mid+1;
19.         while(cur1<=mid)
20.         {
21.             while(cur2<=right && nums[cur1]/2.0 <= nums[cur2]) cur2++;
22.             if(cur2>right) break;
23.             ret += right-cur2+1;
24.             cur1++;
25.         }
26.         int curr1 = left,curr2 = mid+1,i = 0;
27.         while(curr1<=mid && curr2<=right)
28.             tmp[i++] = nums[curr1]<=nums[curr2] ? nums[curr2++] : nums[curr1++];
29.         //处理未遍历完
30.         while(curr1<=mid) tmp[i++] = nums[curr1++];
31.         while(curr2<=right) tmp[i++] = nums[curr2++];
32.         //还原
33.         for(int i = left;i<=right;i++)
34.             nums[i] = tmp[i-left];
35.         return ret;
36.     }

复制代码

这里不是nums[cur2]*2缘故起因是，固然都是32位整数范围内，但是*2可能会导致积超过32位的范围，所以/2.0

解法2：升序

2. int tmp[50005];
3. public:
4. //升序
5.     int reversePairs(vector<int>& nums)
6.     {
7.         return mergeSort(nums,0,nums.size()-1);
8.     }
9.     int mergeSort(vector<int>& nums,int left,int right)
10.     {
11.         int ret = 0;
12.         if(left>=right) return 0;
14.         int mid = (left+right)>>1;
15.         ret += mergeSort(nums,left,mid);
16.         ret += mergeSort(nums,mid+1,right);
17.         //统计翻转对
18.         int cur1 = left,cur2 = mid+1;
19.         while(cur2<=right)
20.         {
21.             while(cur1<=mid && nums[cur1]/2.0 <= nums[cur2]) cur1++;
22.             if(cur1>mid) break;
23.             ret += mid-cur1+1;
24.             cur2++;
25.         }
26.         int curr1 = left,curr2 = mid+1,i = 0;
27.         while(curr1<=mid && curr2<=right)
28.             tmp[i++] = nums[curr1]<=nums[curr2] ? nums[curr1++] : nums[curr2++];
29.         //处理未遍历完
30.         while(curr1<=mid) tmp[i++] = nums[curr1++];
31.         while(curr2<=right) tmp[i++] = nums[curr2++];
32.         //还原
33.         for(int i = left;i<=right;i++)
34.             nums[i] = tmp[i-left];
35.         return ret;
36.     }

复制代码

看到末了，如果对您有所帮助，还请点赞、收藏和关注，我们下期再见！