算法专题七: 分治归并
目录
- 1. 排序数组
- 2. 交易逆序对的总数
- 3. 计算右侧小于当前元素的个数
- 4. 翻转对
1. 排序数组
算法思路: 本道题使用归并的思路进行排序, 先讲数组分为左右两个区间, 然后合并两个有序数组.
class Solution {vector<int> tmp;
public:vector<int> sortArray(vector<int>& nums) {tmp.reserve(nums.size());mergesort(nums,0,nums.size()-1);return nums;}void mergesort(vector<int>& nums,int left,int right){if(left >= right) return;int mid = (right + left)>>1;mergesort(nums,left,mid);mergesort(nums,mid+1,right);int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int i = left; i <= right;i++){nums[i] = tmp[i - left];}}
};
2. 交易逆序对的总数
算法思路:
先找左半部分的逆序对, 然后再找右半部分的逆序对, 最后再一左一右的找逆序对, 找完左半部分和右半部分之后给数组排个序对数组的结果不影响, 而且排完序之后找一左一右的逆序对还简单些, 不由得我们就可以想到此方法和归并排序的思路一样, 只不过再排序的过程中增加了统计逆序对的个数. 这里可以采用两种策略, 第一种固定当前位置的值, 然后找前面有多少数是比我大的, 第二种策略, 固定当前位置的值, 找后面有多少元素是比我小的.
- 首先使用第一种策略, 固定一个数, 在前面找比我大的元素的个数.
当前为升序的排序, 我们归并的时候如果nums[cur1] <= nums[cur2] 时, 此时我们只需要把cur1++就行, 如果nums[cur1]在某一个位置大于nums[cur2]时,此时已经找到了比nums[cur2]大的元素, 那么mid- cur1 + 1这段区间里面的所有值都比nums[cur2]大, 此时统计逆序对的数量即可, 然后再让cur2++, 但是不要往了我们还要排序, 所以这一步写在归并数组那里即可.
那么既然升序可以, 降序可不可以呢?
如图所示, 该数组为降序的时候, 固定cur1, cur2位置时,如果cur1大于cur2则开始统计cur1中大于cur2元素的个数, 看似没有什么问题, 但是如果进入下一次循环中, cur1++之后还有可能大于cur2,此时在统计那不是重复了嘛, 显然结果是错误的
- 第二种策略: 固定一个数, 然后找后面比我小的元素的个数
首先先来看降序的数组, 来统计固定一个位置之后, 后面有多少元素比我小, 当nums[cur1] <= nums[cur2]时, 此时不是我们想要的结果, 我们需要的是nums[cur1]>nums[cur2], 这个时候, 我们统计后面有多少个元素比我小即可, 很显然此时数组是降序的, 所以right - cur2 + 1 即为结果
if(nums[cur1] <= nums[cur2])
tmp[i++] = nums[cur2++];
else
{
ret += right - cur2 + 1;
tmp[i++] = nums[cur1++];
}
反之我们来看一下升序
此时数组为升序, 我们需要找后面比前面小的元素的个数, 当固定到cur1之后, nums[cur1] > nums[cur2]时, 此时开始找结果, 在后面看在mid到cur2之间的这部分都是比nums[cur1]小的, 但是下一次cur2++之后还有可能是小于nums[cur1]的, 所以此时重复统计了 , 结果是错误的.
代码部分:
策略1
class Solution {int tmp[50000];
public:int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}int mergeSort(vector<int>& nums,int left,int right){if(left>=right) return 0;int ret = 0;int mid = (right + left) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);//程序到这里左边与右边已经处理完毕, 现在处理左右int cur1 = left, cur2 = mid + 1, i = 0;//升序 找比当前位置大的个数while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2])tmp[i++] = nums[cur1++];else{ret += mid - cur1 + 1;tmp[i++] = nums[cur2++]; }}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int i = left; i <= right; i++){nums[i] = tmp[i - left];}return ret;}
};
策略2
class Solution {int tmp[50000];
public:int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}int mergeSort(vector<int>& nums,int left,int right){if(left>=right) return 0;int ret = 0;int mid = (right + left) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);//程序到这里左边与右边已经处理完毕, 现在处理左右int cur1 = left, cur2 = mid + 1, i = 0;//降序 找比当前位置小的个数while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2])tmp[i++] = nums[cur2++];else{ret += right - cur2 + 1;tmp[i++] = nums[cur1++]; }}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int i = left; i <= right; i++){nums[i] = tmp[i - left];}return ret;}
};
3. 计算右侧小于当前元素的个数
算法思路:
本道题更上一道题的思路是一模一样的, 上一道题我们采用了策略一的方法, 本道题我们采用策略二, 找后面比当前位置元素小的元素的个数, 但是与上一道题不同的是本道题要求返回对应位置的结果, 这是个问题, 如何解决呢, 我们可以采用哈希的思想, 如果使用哈希表那么如果遇到重复的元素, 我们就无法进行解决, 但是我们可以采用这种思想, 创建一个新的数组, 这个数组中存放的是对应位置原始的下标, 然后这个数组跟着nums一起变化, 但是无论怎样变换, 里面的下标还是最原始的下标位置.
编写代码:
class Solution {vector<int> index;vector<int> ret;int tmpNums[500010];int tmpIndxt[500010];
public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);for(int i = 0;i < n;i++)index[i] = i;mergeSort(nums,0,n-1);return ret;}void mergeSort(vector<int>& nums,int left,int right){if(left >= right) return;int mid = (left + right)>>1;mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);//至此左右已经处理完, 现在处理一左一右int cur1 = left, cur2 = mid+1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmpNums[i] = nums[cur2];tmpIndxt[i++] = index[cur2++];}else{ret[index[cur1]] += right - cur2 + 1;tmpNums[i] = nums[cur1];tmpIndxt[i++] = index[cur1++];}}while(cur1 <= mid){tmpNums[i] = nums[cur1];tmpIndxt[i++] = index[cur1++];}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndxt[i++] = index[cur2++];}for(int i = left; i <= right; i++){nums[i] = tmpNums[i - left];index[i] = tmpIndxt[i - left];}}
};
4. 翻转对
算法思路:
首先我们还是先考虑两个策略. 策略一, 计算后面有多少个元素的两倍比我小, 策略二. 计算前面有多少元素的一半比我大. 不同于前两题, 本道题无法在归并的时候进行计算, 因为这里的比较逻辑和归并的比较逻辑是不同的, 所以这里我在归并逻辑之前采用双指针的方法先进行统计, 然后在进行归并排序.
那么首先来看策略一, 在处理完左右之后并排序之后, 我们处理一左一右的情况, 使用双指针, 计算后面有多少元素的两倍比我小, 如果nums[cur1] <= nums[cur2] * 2, 则说明后面元素的两倍比我大, 那么继续移动cur2, 知道找到cur2的位置两倍比我小, 然后进行统计, 此时cur1++, 进行下一次的统计, 这里cur2还需要回退到mid+1的位置嘛?
答案是不需要的, 因为当前位置cur2位置前面元素的两倍都是比我大的, 那cur1++之后降序, 那么一定也是比我大的, 所以直接统计就可以了, 所以整体的时间复杂度为O(NlogN).
class Solution {int tmp[50000];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums, 0 , nums.size() - 1);}int mergeSort(vector<int>&nums, int left , int right){if(left >= right) return 0;int ret = 0;int mid = (left + right) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);int cur1 = left, cur2 = mid + 1, i = left;while(cur1 <= mid){while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;if(cur2 > right) break;//小优化ret += right - cur2 + 1;cur1++;}//降序cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] >= nums[cur2] ? nums[cur1++] : nums[cur2++];while(cur1<=mid) tmp[i++] = nums[cur1++];while(cur2<=right) tmp[i++] = nums[cur2++];for(int j = left; j <= right; j++)nums[j] = tmp[j]; return ret;}
};
策略二: 找前面有多少元素的一半比我大
其实更策略一的逻辑是类似的, 只不过这里的数组是升序排列的, 找前面有多少元素的一半比我大, 先让cur1走, 如果/2之后大于nums[cur2]则, cur1++, 找到位置之后统计ret, 然后让cur2++,进行下一次的统计, 此时cur1也不需要回去, cur1之前的位置一半都是比cur2小的, 那么cur2++之后一定还是比cur1小, 所以cur2直接++即可.
class Solution {int tmp[50000];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size()-1);}int mergeSort(vector<int>& nums,int left, int right){if(left >= right) return 0;int mid = (left + right) >> 1;int ret = 0;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);int cur1 = left, cur2 = mid + 1, i = left;//升序, 先统计逆序对while(cur2 <= right){while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) cur1++;if(cur1 > mid) break;ret += mid - cur1 + 1; cur2++;} //合并有序数组cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int j = left ; j <= right ; j++)nums[j] = tmp[j];return ret;}
};
完