算法8--归并
目录
- 原理
- 经典例题
- [912. 排序数组](https://leetcode.cn/problems/sort-an-array/description/)
- [LCR 170. 交易逆序对的总数](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/)
- 计算右侧小于当前元素的个数
- [493. 翻转对](https://leetcode.cn/problems/reverse-pairs/description/)
原理
归并算法的原理可以参考归并排序，归并排序算法不仅仅是使用该算法对数据进行排序，重要的是在归并的过程中解决某些问题，从而使一些原本时间复杂度较高的问题降到O(n*log2n)。
经典例题
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);
}
};