当前位置: 首页> 教育> 大学 > 找客户资源的软件_软件商店正版下载_互联网广告联盟_网站访问量

找客户资源的软件_软件商店正版下载_互联网广告联盟_网站访问量

时间:2025/7/11 14:58:26来源:https://blog.csdn.net/2302_78794424/article/details/142675479 浏览次数:0次
找客户资源的软件_软件商店正版下载_互联网广告联盟_网站访问量

目录

一分治-快排

1颜色划分

2快速排序

3第K个最大数

4最小的k个数

二分治-归并 

1归并排序

2交易逆序对的总数

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

4翻转对 


一分治-快排

1颜色划分

oj链接:颜色分类

思路:三指针

类似双指针的移动零:搞三个指针来划分0,1,2区间

i:遍历数组(以它来分析)

left:标记0的最右侧

right:标记2的最左侧 

接下来就是划分区间来讨论

class Solution {
public:void sortColors(vector<int>& nums) {int left = -1,right = nums.size();//边界处理for(int i = 0 ; i < right ; ){if(nums[i] == 0) swap(nums[++left] , nums[i++]);else if(nums[i] == 2) swap(nums[--right] , nums[i]);else i++;}    }
};

2快速排序

oj链接:排序数组

思路:三指针

数组分为三个区间

i:遍历数组(以它来分析)

left:标记<key的最右侧

right:标记>key的最左侧 

接下来就是划分区间来讨论

优化:用随机的方式选择key值

也就是先种一颗随机数种子srand(time(NULL))

key = nums[ rand()%(r-l+1) + l ] (每次递归区间元素个数不同,l也是不同)

class Solution
{
public:vector<int> sortArray(vector<int> &nums){srand(time(NULL));QuickSort(nums, 0, nums.size() - 1);return nums;}void QuickSort(vector<int> &nums, int l, int r){if (l >= r)return;int key = nums[rand() % (r - l + 1) + l], left = l - 1, right = r + 1;for (int i = left + 1; i < right;){if (nums[i] < key)swap(nums[++left], nums[i++]);else if (nums[i] == key)i++;elseswap(nums[--right], nums[i]);}QuickSort(nums, l, left);QuickSort(nums, right, r); // r+1 x i到达r位置停止该位置的数=还是>key是不确定的!}
};

3第K个最大数

oj链接:数组中的第K个最大元素

除了要用到上面的思想,还要在递归之前分类讨论! 

class Solution
{
public:int findKthLargest(vector<int> &nums, int k){srand(time(NULL));return QucikSort(nums, 0, nums.size() - 1, k);}int QucikSort(vector<int> &nums, int l, int r, int k){if (l == r)return nums[l]; // l==r 保证区间是存在的!int key = nums[rand() % (r - l + 1) + l], left = l - 1, right = r + 1;for (int i = l; i < right;) // i<r X{if (nums[i] < key)swap(nums[++left], nums[i++]); // left++ Xelse if (nums[i] == key)i++;elseswap(nums[--right], nums[i]); // right-- X}int b = right - left - 1, c = r - right + 1; // b个数的区间 [left+1,right-1]if (c >= k)return QucikSort(nums, right, r, k);else if (b + c >= k)return key;elsereturn QucikSort(nums, l, left, k - b - c);}
};

4最小的k个数

oj链接:库存管理 III

与上题类似,但有细节:a > k不用 a==k:因为a == k直接返回就行了不用在找了!

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));QuickSlectSort(stock,0,stock.size()-1,cnt);return {stock.begin(),stock.begin()+cnt};}void QuickSlectSort(vector<int>& stock,int l,int r,int k){if(l>=r) return;int left=l-1,right=r+1,i=l;int key=stock[rand()%(r-l+1)+l];while(i<right){if(stock[i]<key) swap(stock[i++],stock[++left]);else if(stock[i]>key) swap(stock[i],stock[--right]);else i++;}//分情况int a=left-l+1,b=right-left-1,c=r-right+1;if(a>k) QuickSlectSort(stock,l,left,k);else if(a+b>=k) return;else QuickSlectSort(stock,right,r,k-a-b); }
};

二分治-归并 

1归并排序

oj链接:排序数组 

class Solution {
public:vector<int> tmp;vector<int> sortArray(vector<int>& nums) {tmp.resize(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=left+(right-left)/2;MergeSort(nums,left,mid);MergeSort(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;//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交易逆序对的总数

oj链接:交易逆序对的总数

策略:把数组分为2段区间:

1.到左区间找找逆序对后排序

2.到右区间找找逆序对后排序

3.左右区间找找逆序对后排序

可以自己画图来看看结果对不对

其实这个过程就是归并排序的过程

class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& record) {tmp.resize(record.size());return MergeSort(record,0,record.size()-1);}int MergeSort(vector<int>& record,int l,int r){if(l>=r) return 0;int mid=l+(r-l)/2;int cnt=0;cnt+=MergeSort(record,l,mid);cnt+=MergeSort(record,mid+1,r);int cur1=l,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=r){if(record[cur1]<=record[cur2]){tmp[i++]=record[cur1++];}else{//升序cnt+=mid-cur1+1;tmp[i++]=record[cur2++];}}while(cur1<=mid) tmp[i++]=record[cur1++];while(cur2<=r) tmp[i++]=record[cur2++];for(int j=l;j<=r;j++) record[j]=tmp[j-l];return cnt;}};class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& record) {tmp.resize(record.size());return MergeSort(record,0,record.size()-1);}int MergeSort(vector<int>& record,int l,int r){if(l>=r) return 0;int mid=l+(r-l)/2;int cnt=0;cnt+=MergeSort(record,l,mid);cnt+=MergeSort(record,mid+1,r);int cur1=l,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=r){if(record[cur1]<=record[cur2]){tmp[i++]=record[cur2++];}else{//降序cnt+=r-cur2+1;tmp[i++]=record[cur1++];}}while(cur1<=mid) tmp[i++]=record[cur1++];while(cur2<=r) tmp[i++]=record[cur2++];for(int j=l;j<=r;j++) record[j]=tmp[j-l];return cnt;}};

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

oj链接:计算右侧小于当前元素的个数

解法:

1.使用上题的策略2:当前元素的后面有多少个比我小

2.关键是当前元素对应的原始数组下标我怎么知道?

有哈希表进行下标绑定? --> 解决不了重复元素的问题

做法:用哈希表的思想创建index数组(保存元素下标)与元素进行绑定

那么在归并时就需要用到两个辅助数组进行归并

 

class Solution {
public:vector<int> tmpnum;vector<int> tmpindex;vector<int> ret;vector<int> index;vector<int> countSmaller(vector<int>& nums) {int n=nums.size();tmpnum.resize(n),tmpindex.resize(n);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(right<=left) return;int mid=left+(right-left)/2;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]){tmpnum[i]=nums[cur2];tmpindex[i++]=index[cur2++];} else{ret[index[cur1]]+=right-cur2+1;tmpnum[i]=nums[cur1];tmpindex[i++]=index[cur1++];}}while(cur1<=mid){tmpnum[i]=nums[cur1];tmpindex[i++]=index[cur1++];}while(cur2<=right){tmpnum[i]=nums[cur2];tmpindex[i++]=index[cur2++];}for(int i=left;i<=right;i++){nums[i]=tmpnum[i-left];index[i]=tmpindex[i-left];}}
};

4翻转对 

 oj链接:翻转对

与前2道题类似:注意翻转对的条件:nums[i] > 2*nums[j] 

这个就不能很好的与归并排序匹配了!

但解决思路也是一样:在归并两个有序数组之前进行统计即可(就不是变合变统计)

class Solution {
public:int ret=0;vector<int> tmp;int reversePairs(vector<int>& nums) {tmp.resize(nums.size());MergeSort(nums,0,nums.size()-1);return ret;}void MergeSort(vector<int>& nums,int l,int r){if(l>=r) return;int mid=l+(r-l)/2;MergeSort(nums,l,mid);MergeSort(nums,mid+1,r);int cur1=l,cur2=mid+1,i=0;int ptr1=cur1,ptr2=cur2;while(ptr1<=mid){while(ptr2<=r&&nums[ptr1]<=2*(long long)nums[ptr2]) ptr2++;ret+=r-ptr2+1;ptr1++;}while(cur1<=mid&&cur2<=r){tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur2++]:nums[cur1++];//降序}while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=r) tmp[i++]=nums[cur2++];for(int i=l;i<=r;i++) nums[i]=tmp[i-l];}
};

 以上便是全部内容,有错误欢迎在评论区指正,感谢你的观看!

 

 

关键字:找客户资源的软件_软件商店正版下载_互联网广告联盟_网站访问量

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: