1.排序数组
//分治-归并
class Solution {
int tmp[50010];
public:
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums,0,nums.size()-1);
return nums;
}
void mergeSort(vector<int>& nums,int left,int right)
{
if(left>=right) return;
//1.选择中间点划分区间
int mid = (left+right)>>1;
//[left,mid][mid+1,right]
//2.将左右两区间排序
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
//3.合并两个有序数组
int cur1 = left,cur2 = mid+1,i=0;
while(cur1<=mid && cur2<=right)
{
tmp[i++] = nums[cur1]>=nums[cur2]?nums[cur2++]:nums[cur1++];
}
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-left];
}
}
};
2.数组中的逆序对
class Solution {
int tmp[50010];
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;
//1.选择中间元素划分区间
int mid = (left+right)>>1;
//[left,mid][mid+1,right]
//2.计算左右区间的逆序对的个数
ret += mergeSort(nums,left,mid);
ret += mergeSort(nums,mid+1,right);
//3.计算一左一右逆序对的个数+合并两个有序数组
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 j=left;j<=right;j++)
{
nums[j] = tmp[j-left];
}
return ret;
}
};
3.计算右侧小于当前元素的个数
class Solution {
vector<int> ret;
vector<int> index;//记录nums当前元素的原始下标
int tmpNums[500010];
int tmpIndex[500010];
public:
vector<int> countSmaller(vector<int>& nums) {
//计算当前元素之后,有多少个比我小(降序)
int n = nums.size();
ret.resize(n);
index.resize(n);
//初始化index数组
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;
//1.选择中间元素划分区间
int mid = (left+right)>>1;
//[left,mid][mid+1,right]
//2.将左右区间进行排序
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
//3.处理一左一右的情况
int cur1 = left,cur2 = mid+1,i=0;
while(cur1<=mid&& cur2<=right)//降序
{
if(nums[cur1]<=nums[cur2])
{
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
else
{
ret[index[cur1]] += right-cur2+1;
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
}
while(cur1<=mid)
{
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
while(cur2<=right)
{
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
//还原
for(int j=left;j<=right;j++)
{
nums[j] = tmpNums[j-left];
index[j] = tmpIndex[j-left];
}
}
};
4.翻转对
//计算当前元素之前,有多少元素的一半比我大--升序
class Solution {
int tmp[50010];
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;
//1.选择中间元素划分区间
int mid = (left+right)>>1;
//[left,mid][mid+1,right]
//2.计算左右区间翻转对的个数
ret += mergeSort(nums,left,mid);
ret += mergeSort(nums,mid+1,right);
//3.先计算翻转对的个数
int cur1 = left,cur2 = mid+1,i=0;
while(cur2<=right)//升序的情况
{
while(cur1<=mid && nums[cur1]/2.0<=nums[cur2]) cur1++;
if(cur1 > mid)
break;
ret += mid-cur1+1;
cur2++;
}
//4.合并两个有序数组
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-left];
}
return ret;
}
};
//计算当前元素后面,有多少元素的两倍比我小--降序
class Solution {
int tmp[50010];
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;
//1.选择中间元素划分区间
int mid = (left+right)>>1;
//[left,mid][mid+1,right]
//2.计算左右区间翻转对的个数
ret += mergeSort(nums,left,mid);
ret += mergeSort(nums,mid+1,right);
//3.先计算翻转对的个数
int cur1 = left,cur2 = mid+1,i=0;
while(cur1<=mid)//降序的情况
{
while(cur2<=right && nums[cur1]/2.0<=nums[cur2]) cur2++;
if(cur2 > right)
break;
ret +=right-cur2+1;
cur1++;
}
//4.合并两个有序数组
cur1 = left,cur2 = mid+1;
while(cur1<=mid && cur2<=right)//降序
{
tmp[i++] = nums[cur1]<=nums[cur2]?nums[cur2++]:nums[cur1++];
}
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-left];
}
return ret;
}
};
原文地址:https://blog.csdn.net/m0_55283616/article/details/134526353
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_8855.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。