算法8--归并

原理

归并算法的原理可以参考归并排序，归并排序算法不仅仅是使用该算法对数据进行排序，重要的是在归并的过程中解决某些问题，从而使一些原本时间复杂度较高的问题降到O(n*log2ⁿ)。

经典例题

912. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

这里可以使用归并排序解决：

class Solution {
public:void MySort(vector<int>& nums,int left,int right){if(left>=right){return;}int mid=(left+right)/2;MySort(nums,left,mid);MySort(nums,mid+1,right);int pos1=left;int pos2=mid+1;int end1=mid;int end2=right;vector<int> tmp;while(pos1<=end1&&pos2<=end2){if(nums[pos1]<nums[pos2]){tmp.push_back(nums[pos1]);++pos1;}else if(nums[pos1]>nums[pos2]){tmp.push_back(nums[pos2]);++pos2;}else{tmp.push_back(nums[pos1]);tmp.push_back(nums[pos2]);++pos1;++pos2;}}while(pos1<=end1){tmp.push_back(nums[pos1]);++pos1;}while(pos2<=end2){tmp.push_back(nums[pos2]);++pos2;}int i=left;for(auto e:tmp){nums[i++]=e;}}vector<int> sortArray(vector<int>& nums) {if(0==nums.size()){return nums;}MySort(nums,0,(int)nums.size()-1);return nums;}
};

LCR 170. 交易逆序对的总数

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

排降序，归并过程中计算逆序对

class Solution {
public:int GetAnswer(vector<int>& record,int left,int right){if(left>=right){return 0;}int mid=(left+right)/2;int count=GetAnswer(record,left,mid)+GetAnswer(record,mid+1,right);int pos1=left;int pos2=mid+1;int end1=mid;int end2=right;vector<int> tmp;while(pos1<=end1&&pos2<=end2){if(record[pos1]<record[pos2]){tmp.push_back(record[pos2++]);}else if(record[pos1]>record[pos2]){tmp.push_back(record[pos1++]);count+=end2-pos2+1;}else{tmp.push_back(record[pos2++]);}}while(pos1<=end1){tmp.push_back(record[pos1++]);}while(pos2<=end2){tmp.push_back(record[pos2++]);}for(auto e:tmp){record[left++]=e;}return count;}int reversePairs(vector<int>& record) {if(0==record.size()){return 0;}return GetAnswer(record,0,record.size()-1);}
};

计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

只需每个元素都绑定好数组下标，再进行归并排序即可，同时为了避免数组的开辟释放，可以提前开好足够的数组空间直接在该数组上操作即可，从而得到一定的优化。

class Solution {
public:void GetAnswer(vector<vector<int>>&nums,int left,int right){if(left>=right){return;}int mid=(left+right)/2;GetAnswer(nums,left,mid);GetAnswer(nums,mid+1,right);if(nums[left][0]==nums[mid][0]&&nums[mid][0]==nums[mid+1][0]&&nums[mid+1][0]==nums[right][0]){return;}int pos1=left;int pos2=mid+1;int end1=mid;int end2=right;vector<vector<int>> tmp;tmp.reserve(right-left+1);while(pos1<=end1&&pos2<=end2){if(nums[pos1][0]<nums[pos2][0]){tmp.push_back(nums[pos2++]);}else if(nums[pos1][0]>nums[pos2][0]){nums[pos1][1]+=end2-pos2+1;tmp.push_back(nums[pos1++]);}else{tmp.push_back(nums[pos2++]);}}while(pos1<=end1){tmp.push_back(nums[pos1++]);}for(auto& e:tmp){nums[left++]=e;}}vector<int> countSmaller(vector<int>& nums) {vector<vector<int>> tmp(nums.size(),vector<int>(3,0));int i=0;for(;i<nums.size();++i){tmp[i][0]=nums[i];tmp[i][2]=i;}GetAnswer(tmp,0,nums.size()-1);vector<int> ans(nums.size(),0);for(auto &e:tmp){ans[e[2]]=e[1];}return ans;}
};

493. 翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。

排降序归并
解法一：归并过程中，如果：

• nums [left]>2*nums[right]：left移入tmp1中，计算翻转对，++left
• nums[right] <= nums [left] <= 2*nums[right]：right移入tmp2中，++right
• nums [left] < nums[right]：right移入tmp1中，++right

解法二：
对左右两个部分，先计算完所有翻转对，再合并

class Solution {
public:int GetAnswer(vector<int>& record, int left, int right) {if (left >= right) {return 0;}int mid = (left + right) / 2;int count = GetAnswer(record, left, mid) + GetAnswer(record, mid + 1, right);int pos1 = left;int pos2 = mid + 1;int end1 = mid;int end2 = right;vector<int> tmp1;vector<int> tmp2;while (pos1 <= end1 && pos2 <= end2) {if (record[pos1] < record[pos2]) {if((long long int)record[pos1] >2* (long long int)record[pos2]){count += end2 - pos2 + 1;tmp2.push_back(record[pos1++]);}else{tmp1.push_back(record[pos2++]);}}else {if((long long int)record[pos1] >2* (long long int)record[pos2]){count += end2 - pos2 + 1;tmp1.push_back(record[pos1++]);}else{tmp2.push_back(record[pos2++]);}}}while (pos1 <= end1) {tmp1.push_back(record[pos1++]);}while (pos2 <= end2) {tmp1.push_back(record[pos2++]);}vector<int> tmp;for(pos1=0,pos2=0;pos1<tmp1.size()&&pos2<tmp2.size();){if(tmp1[pos1]>tmp2[pos2]){tmp.push_back(tmp1[pos1++]);}else if(tmp1[pos1]<tmp2[pos2]){tmp.push_back(tmp2[pos2++]);}else{tmp.push_back(tmp1[pos1++]);tmp.push_back(tmp2[pos2++]);}}while(pos1<tmp1.size()){tmp.push_back(tmp1[pos1++]);}while(pos2<tmp2.size()){tmp.push_back(tmp2[pos2++]);}for (auto e : tmp) {record[left++] = e;}return count;}int reversePairs(vector<int>& nums) {return GetAnswer(nums,0,nums.size()-1);}
};