长沙模板建站源码,电子商务网站开发系统,北京网站制作工作室,个人网站模板二分力扣题
一#xff1a;搜索二维矩阵
74. 搜索二维矩阵
按照题意#xff1a;直接利用二维数组转换成一维数组进行求解 方法一#xff1a;普通等于的二分查找
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {t…二分力扣题
一搜索二维矩阵
74. 搜索二维矩阵
按照题意直接利用二维数组转换成一维数组进行求解 方法一普通等于的二分查找
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {this-m matrix.size();this-n matrix[0].size();int l0;int rm*n-1; //(m-1)*n(n-1) r坐标(m-1,n-1)int mid;while(lr){mid(lr)1;auto [i,j]getIndex(matrix,mid);//三种分支if(matrix[i][j]target) lmid1;else if(matrix[i][j]target) rmid-1;else return true;//}//没找到return false;}private:int m, n;// 一维转换二维pairint, int getIndex(vectorvectorint matrix, int index) {return {index / n, index % n};}
};方法二按照求最后一个等于
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {this-m matrix.size();this-n matrix[0].size();int l0;int rm*n-1; //(m-1)*n(n-1) r坐标(m-1,n-1)int mid;//最后一个等于扩大lwhile(lr){mid(lr)1;auto [i,j]getIndex(matrix,mid);if(matrix[i][j]target){//最后一个lmid1;}else{rmid-1;}}//r要求0if(r0) return false;auto [i,j]getIndex(matrix,r);//下标已经合法了return matrix[i][j]target?true:false;}private:int m, n;// 一维转换二维pairint, int getIndex(vectorvectorint matrix, int index) {return {index / n, index % n};}
};也可以按照第一个等于注意if条件是““ //第一个等于缩小rwhile(lr){mid(lr)1;auto [i,j]getIndex(matrix,mid);//合法就缩小rif(matrix[i][j]target){rmid-1;}else{lmid1;}}//l要求 ---(m*n-1)if(lm*n-1) return false;auto [i,j]getIndex(matrix,l);//注意是l//下标已经合法了return matrix[i][j]target?true:false;二不重复元素找最小值
153. 寻找旋转排序数组中的最小值
不是只有单调序列才能二分查找只要题目属于分段单调的而且能够找到分界点就可以二分。 本题就是一个不含重复元素的单调序列把它的后半部分移到了数组开头位置。 比如[1,3,5,7,9]-[7,9 || 1,3,5] 序列具备两段都是单调函数而且前一段序列值一定大于后一半 想要找的最小值满足 它一定比最右端元素小而且是比最右端元素小的最小值 而且比最右端元素大的值一定不是最小值 相当于找第一个最右端元素的值 //6789// 1234//找到第一个最右端的数int findMin(vectorint nums) {int l0;int rnums.size()-1;while(lr){int mid(lr)1;if(nums[mid]nums[r]){rmid;//注意保留mid}else{lmid1;}}return nums[l];//注意返回的是下标对应的值}也可以比较第一个值nums[0]但是要注意如果[l,r]不存在转折也就是满足递增提前判断 如果mid对应值nums[0],最低谷一定在mid右端lmid1 如果mid对应值值nums[0]最低谷可能是mid或mid左边rmid int findMin(vectorint nums) {int l0;int rnums.size()-1;while(lr){//如果[l,r]是一段递增if(nums[l]nums[r]){return nums[l];}int mid(lr)/2;//存在低谷if(nums[mid]nums[0]){lmid1;}else{rmid;}}return nums[l];}三搜索旋转数组值
33. 搜索旋转排序数组 先确定mid再寻找值确定mid与target无关只跟两侧有关 本题的数组序列是递增数列的一部分移动到了前面 比如1 3 5 7 9 - 7 9 || 1 3 5 满足两部分都递增而且前一部分比后一部分大 解题时
首先判断mid在哪一个递增分段上有两种可能
如果mid落在左分支即nums[mid]nums[l] 此时只需要判断target在红色还是不在红色 nums[l]targetnums[mid] 在红色rmid-1不在红色lmid1
如果mid落在右分支即nums[mid]nums[l] 同上面判断target是否落在红色区间 nums[mid]targetnums[r] 在红色lmid1不在红色rmid-1
代码 int search(vectorint nums, int target) {int l 0;int r nums.size() - 1;while (l r) {int mid (l r) 1;// 返回结果if (nums[mid] target) {return mid;}if (nums[mid] nums[l]) {// 判断taget所在位置if (target nums[l] target nums[mid]) {r mid - 1;} else {l mid 1;}} else {if (target nums[mid] target nums[r]) {l mid 1;} else {r mid - 1;}}}// 没找到return -1;}还可以判断 while(lr){int mid(lr)1;if(nums[mid]target) return mid;else if(nums[mid]nums[r]){//midif(nums[mid]target targetnums[r]){lmid1;}else{rmid-1;}}else{if(targetnums[l]nums[mid]target){rmid-1;}else{lmid1;}}}也就是判断mid位置就两种 大于等于nums[l]小于等于nums[r] 都只判断一个就可以确定mid 四选举人
911. 在线选举
思路 既然是统计大小一定会用到查找表set或map) 题目给出的是某一时刻投给了哪个人那么TopVotedCandidate()计算某一个时刻哪个人票数最多 然后q(t)计算是任意t时间点的获胜人数只有某一时间点获胜人数的信息所以二分查找 —最后一个t的时间点然后直接返回对应获胜者即可
map统计频次mp[人]票数用winners存储当前时间点获胜的人
class TopVotedCandidate {
public:TopVotedCandidate(vectorint persons, vectorint times) {this-timestimes;int maxWinner0;//当前最大票数for(auto val:persons){mp[val];//对应人票数1if(mp[val]mp[maxWinner]){//题目要求相等取最近获胜者需要更新maxWinnerval;}winners.push_back(maxWinner);}}int q(int t) {//查找最后一个t的时刻int l0;int rtimes.size()-1;while(lr){int mid(lr1)1;//别忘了1if(times[mid]t){lmid;//扩大l}else{rmid-1;}}return winners[l];}
private:unordered_mapint,int mp;//mp[选举人]票数vectorint winners;//当前t时刻的获胜者vectorint times;//为q(t)传参
};或者也可以定义最大值记录当前获胜者的最大票数和得到最大票数的优胜者 int maxVotes0;//当前最大票数int top0;//要存入的获胜者for(auto val:persons){mp[val];//对应人票数1if(mp[val]maxVotes){//题目要求相等取最近获胜者需要更新maxVotesmp[val];topval;//当前人}winners.push_back(top);}方法二
直接计算mp[当前时间点]获胜者只是需要开辟新数组来记录最大值
class TopVotedCandidate {
public:TopVotedCandidate(vectorint persons, vectorint times) {int maxVotes0;votesvectorint(times.size());for(int i0;itimes.size();i){votes[persons[i]];//persons[i]这个人的票数1//因为出现i-1if(i0){maxVotesvotes[persons[i]];mp[times[i]]persons[i];continue;}if(votes[persons[i]]maxVotes){maxVotesvotes[persons[i]];//当前时刻的的票最多人mp[times[i]]persons[i];}else{mp[times[i]]mp[times[i-1]];}}}int q(int t) {while(!mp.count(t)){t--;}return mp[t];}
private://mp[time]persons;unordered_mapint,int mp;vectorint votes;
};/*** Your TopVotedCandidate object will be instantiated and called as such:* TopVotedCandidate* obj new TopVotedCandidate(persons, times);* int param_1 obj-q(t);*/三分查找
问题 已知函数 () 在区间 [l,r] 上单峰且连续求 () 在 [l,r]上的极值 也就是说三分查找适用于存在局部极大值或局部极小值的函数来找到极值点 如图在定义域[L,R]内部取两点lmid和rmid,整个函数被这两个点分成了三块区域通过这两个值的大小来舍弃某一些区间来缩小查找范围 查找过程 有高峰的函数只要满足nums[lmid]nums[rmid],那么极大值一定在lmid的右边也就是让llmid1; 同理如果nums[rmid]nums[lmid],极大值一定在rmid左边也就是rrmid-1
寻找峰值
162. 寻找峰值
为了能保证每次取舍一半区间让[l,r]内部取的lmid和rmid取值为
lmid(lr)1,也就是中点rmidlmid偏移量可以是lmid1 当然lmid和rmid也可以是三等分点 int findPeakElement(vectorint nums) {//这里题目一定会有解l和r直接取两端即可int l0;int rnums.size()-1;while(lr){//在[l,r]内部取lmid和rmidint lmid(lr)1;int rmidlmid1;//进行区间取舍if(nums[lmid]nums[rmid]){llmid1;}else{rrmid-1;}}return l;//r}这里的等号取不取对本题而言没有影响 二分判定枚举
二分法还有一个重要应用是 枚举答案尤其是值域上的二分枚举。 注意:要先确定存在二段性才可以用二分枚举答案 引例猜数字
374. 猜数字大小 使用相加除二可能会溢出 mid (l r) / 2;如果 l 和 r 足够大mid值会导致int 数据类型越界如果超出int的最大范围 那么结果变成负数 防溢出写法使用减法r - l不会超出最大的整型范畴 mid l (r - l)/2;int guessNumber(int n) {//数字一定在1~n中int l1;int rn;//二分猜值while(lr){int midl(r-l)/2;//防止溢出int ansguess(mid);//调用接口//三种if(ans-1){//要猜的更小rmid-1;}else if(ans1){lmid1;}else{//return mid;}}return -1;}可以选用第一个大于等于或最后一个小于等于注意mid的向上和向下取值 int guessNumber(int n) {//数字一定在1~n中int l1;int rn;//二分猜值while(lr){int midl(r-l)/2;//防止溢出int ansguess(mid);//调用接口//找第一个if(ans0){rmid;}else{lmid1;}}return l;}int guessNumber(int n) {//数字一定在1~n中int l1;int rn;//二分猜值while(lr){//向上取整int midl1(r-l)/2;//防止溢出int ansguess(mid);//调用接口//找第一个if(ans0){lmid;}else{rmid-1;}}return l;}对于一个最优化问题
求解求出这个最优解判定判断这个解是否合法 p问题就是能够多项式时间求出问题的解 np问题就是能够多项式时间验证问题的解 二分答案法
如果解空间具有单调性那么利用二分加上判定就相当于枚举整个问题的解这种求出最优解的方法叫二分答案法 也就是通过判定算法来枚举解空间一样可以求出最优解 比如 猜数问题在解空间每次选择中间值通过判定猜的数是大了还是小了一样可以得到最终结果 一运送包裹能力
1011. 在 D 天内送达包裹的能力
也就是想找到一个值W这个值能满足在days天顺序运送完货物而且W是最小的 这道题满足单调性W值越大那么越能在days天运送完货物 思路首先写出判定函数isValid(),该函数可以判定解的合法性然后用二分查找结合该函数就能找到最小值 注意 W最小值就是所有货物取最大也就是一下只运送一个货物但是days会很长W最大值就是一次运送完所有货物但是W值一定不是想要的最小值判定函数就是给定的W值能否满足在days天内运送完所有货物。 说白了就是枚举W的所有可能但是由于具备单调性W能在days天运送完那么W1一定也能在days天内运完。所以可以利用二分枚举所有可能然后来利用判定函数来取舍区间 解
class Solution {
public:int shipWithinDays(vectorint weights, int days) {int l0;int r0;//初始化值l取最小r取最大for(auto val:weights){lmax(l,val);rval;}//二分给定W值while(lr){int mid(lr)1;if(isValid(weights,days,mid)){rmid;//缩小mid值}else{lmid1;}}return l;}
private://给定值W能否在days天内完成所有物品运输bool isValid(vectorint weights,int days,int W){//尽量把货物塞满W,多了就下一天再搬贪心int sum0;int time1;//第一天for(int i0;iweights.size();i){if(sumweights[i]W){sumweights[i];}else{//这天超过了开始下一天的搬运time1;sumweights[i];}}return timedays;//只要time比规定时间小就完成}
};二分割数组最大值
410. 分割数组的最大值 这道题其实和运送包裹完全一样。 思路
给定一个用函数来判定值不超过V的数字和划分一组看组数是否小于等于k然后利用二分来进行求解取满足判定函数的最小mid值缩小l
class Solution {
public:int splitArray(vectorint nums, int k) {int l0;int r0;//最小l每一个单组成组最大r:只划分一组for(auto val:nums){lmax(l,val);rval;}//二分while(lr){int mid(lr)1;if(isValid(nums,k,mid)){rmid;}else{lmid1;}}return l;}
private://将nums以V划分组看划分的个数是否kbool isValid(vectorint nums,int k,int V){int sum0;int time1;//从第一组开始分for(int i0;inums.size();i){if(sumnums[i]V){sumnums[i];}else{//重新划分新组time;sumnums[i];}}return timek;}
};这里可以二分查找的原因 解具备单调性因为假设划分k组后某组最大值是V那么V1,V2,VN也一定满足题目的要求。 也就是说可以用二分枚举V然后通过判定得到能符合要求的最小值。 假设划分k组后最大值为V。那么划分k-n组一定满足最大值小于V。 题目要求最大值最小所以可以找到恰好符合的临界条件 三制作花最少天数
1482. 制作 m 束花所需的最少天数
题目的解满足单调性
假定T天就能完成k组m束花的要求那么T1,T2,…也一定可以
假设T天可以采摘超过m束花那么最优解可能在T-1,T-2,…里面取得 class Solution {
public:int minDays(vectorint bloomDay, int m, int k) {int MAX(1e9)1;int l1;//第一天就全采摘了int rMAX;//题目给定最大1while(lr){int mid(lr)1;if(isValid(bloomDay,m,k,mid)){rmid;//缩小r,因为求最短T}else{lmid1;}}return lMAX?-1:l;}
private://给定时间T问能否在T天内采摘m束花每束花必须满足连续相邻k朵bool isValid(vectorint bloomDay,int m,int k,int T){int continuous0;//计算连续int time0;//初始化不能采摘for(int i0;ibloomDay.size();i){if(bloomDay[i]T){//开花了continuous;//满足条件更新结果if(continuousk){time;continuous0;}}else{continuous0;//断了重新计数}}return timem;//至少要采摘m}
};四能吃完香蕉的最少天数
875. 爱吃香蕉的珂珂 也就是定义好速度V然后二分枚举求出整个最小V 题目中 如果pile[i]V,也就是1h能吃V根数量多于该堆数量那么取时间一小时 所以相当于pile[i]/V向上取整 可以利用余数来选择是否加一也可以 class Solution {
public:int minEatingSpeed(vectorint piles, int h) {int l1;int r1e9;while(lr){int mid(lr)1;if(isValid(piles,h,mid)){rmid;//缩小r}else{lmid1;}}return l;}
private://给定速度V在h小时内能否吃完所有香蕉bool isValid(vectorint piles,int h,int V){int hour0;//千万别忘了初始值0for(int i0;ipiles.size();i){if(piles[i]%V0){hourpiles[i]/V;}else{hourpiles[i]/V1;}}return hourh;}
};计算hour还可以 for(auto pile:piles){hourpile/V(pile%V0?0:1); }也可以 for(int i0;ipiles.size();i){hour(piles[i]V-1)/V;// hour(piles[i]-1)/V1;}注意
因为题目限制了珂珂一个小时之内只能选择一堆香蕉吃因此速度最大值就是这几堆香蕉中数量最多的那一堆。 int r1; for(auto val:piles) rmax(r,val); 排序 基于比较的排序算法时间复杂度不能突破O(NlogN) 简单证明 比较排序 非比较排序 选插冒三种初级排序
选择排序
// 选择排序vectorint sortArray(vectorint nums) {int n nums.size();for (int i 0; i n - 1; i) {int minIndex i;for (int j i 1; j n; j) {if (nums[j] nums[minIndex]) {minIndex j;}}swap(nums[i], nums[minIndex]);}return nums;}插入排序 直接交换
//插入排序vectorint sortArray(vectorint nums) {int nnums.size();for(int i1;in;i){//i从1开始默认第一个有序//结束条件是j0因为访问j-1for(int ji;j0 nums[j]nums[j-1];j--){swap(nums[j],nums[j-1]);}}return nums;}优化 可以不直接交换记住值然后后一个值等于前一个值停止时值改成最先记录的 //插入排序vectorint sortArray(vectorint nums) {int nnums.size();for(int i1;in;i){//i从1开始默认第一个有序int enums[i];int j;for(ji;j0 nums[j-1]e;j--){nums[j]nums[j-1];}nums[j]e;}return nums;冒泡排序 把大的依次放到后面每一次冒泡都会得到一个最大值冒泡次数数组长度-1 // 冒泡排序vectorint sortArray(vectorint nums) {int n nums.size();for (int i 0; i n - 1; i) {//冒泡长度-1次for (int j 0; j n - 1 - i; j) {if (nums[j] nums[j 1]) { // 大的放后面swap(nums[j], nums[j 1]);}}}return nums;}当然也可以从n-1开始小的放前面 如果在一次遍历中没有进行任何交换可以提前结束排序因为这意味着数列已经排序完成。
优化引入是否交换过的标志 // 冒泡排序vectorint sortArray(vectorint nums) {int n nums.size();bool flagfalse;//是否交换过for(int i0;in-1;i){for(int j0;jn-1-i;j){//大的后放if(nums[j]nums[j1]){swap(nums[j],nums[j1]);flagtrue;}}if(!flag) break;}return nums;}归并排序
class Solution {
public:vectorint sortArray(vectorint nums) {mergeSort(nums,0,nums.size()-1);return nums;}
private:void merge(vectorint nums,int l,int mid,int r){int il;int jmid1;int k0;//创建aux存储合并结果int* auxnew int[r-l1];while( imid jr){if(nums[i]nums[j]){aux[k]nums[i];}else{aux[k]nums[j];}}//判断while中是哪个条件不满足while(imid){aux[k]nums[i];}while(jr){aux[k]nums[j];}//把aux结果赋值给nums//注意aux:[0,r-l1) nums:[l,r]/*for(int i0;ir-l1;i){nums[il]aux[i];}*/for(int il;ir;i){nums[i]aux[i-l];}}void mergeSort(vectorint nums,int l,int r){if(lr) return;int mid(lr)1;//分mergeSort(nums,l,mid);mergeSort(nums,mid1,r);//治合并两个结果merge(nums,l,mid,r);}
};也可以改写merge 条件1imid 条件2jr if(条件1不满足) else if(条件2不满足) else if (此时判断)//此时条件1和条件2一定满足了 void merge(vectorint nums,int l,int mid,int r){int il;int jmid1;//创建aux存储合并结果int* auxnew int[r-l1];for(int k0;kr-l1;k){if(imid){aux[k]nums[j];}else if(jr){aux[k]nums[i];}//imid jrelse if(nums[i]nums[j]){aux[k]nums[i];}else{aux[k]nums[j];}}//还原nums//for(int il;ir;i){// nums[i]aux[i-l];//}for(int i0;ir-l1;i){nums[il]aux[i];}}for(int k0;kr-l1;k){if(imid jr){if(nums[i]nums[j]){aux[k]nums[i];}else{aux[k]nums[j];}}else if(imid){//jraux[k]nums[i];}else{aux[k]nums[j];}}初级排序的优化排序
堆排序
简洁实现,直接利用stl 由于是从小到大可以存值的负数的大根堆然后赋值取负号 vectorint sortArray(vectorint nums) {priority_queueint pq;//首先建堆for(int i0;inums.size();i){pq.push(-nums[i]);}//出堆for(int i0;inums.size();i){nums[i]-pq.top();//负号pq.pop();}return nums;}当然直接建立小根堆也行 priority_queueint,vectorint,greaterint pq;//大的沉底 定义采用向下调整函数 思路 首先对数组原地调整成大顶堆 注意,因为数组从0开始k的左孩子k*21右孩子k *22k的父节点k-1)/2从最后一个父节点不断向上调整至根节点就可以得到堆 接下来要从小到大输出 每次把堆顶元素往后放然后从0开始重新调整堆 class Solution {
public:vectorint sortArray(vectorint nums) {int nnums.size();//从第一个非叶子结点向下调整直至到根for(int i(n-2)/2;i0;i--){shiftDown(nums,n,i);}//从小到大把根顶后移for(int in-1;i0;i--){swap(nums[0],nums[i]);shiftDown(nums,i,0);//注意[0,n-2],所以传n-1}return nums;}
private://向下调整---数组长度从k开始向下调整void shiftDown(vectorint nums,int n,int k){//注意k*21是左孩子k*22是右孩子while(k*21n){int jk*21;if(j1n nums[j1]nums[j]) j;//比较父节点和儿子最大结点jif(nums[k]nums[j]){swap(nums[k],nums[j]);}else{break;}kj;//k指向交换后的位置}}
};优化:记录值赋值代替交换
void shiftDown(vectorint nums,int n,int k){//注意k*21是左孩子k*22是右孩子int enums[k];while(k*21n){int jk*21;if(j1n nums[j1]nums[j]) j;//比较父节点和儿子最大结点jif(nums[j]e){nums[k]nums[j];//父儿子}else{break;}kj;//k指向交换后的位置}nums[k]e;}希尔排序不常用
利用增量分组对插入排序进行优化 这里最后的0如果选用插入排序会跨越整个数组影响算法性能 希尔排序的做法
先将元素进行分组每次先在组内进行排序尽量让元素可以在早期尽量多地移动。 选择分组的跨度是5跨度是数组长度的一半。 相同颜色的元素为一组 在组内进行插入排序 接着将跨度缩小一半从5变成2接着重复上述逻辑 最后跨度设为1总体进行插入排序得到结果。 vectorint sortArray(vectorint nums) {int nnums.size();int hn/2;//假设以一半为增量while(h0){for(int ih;in;i){//从增量往前插入for(int ji;jh nums[j]nums[j-h];j-h){swap(nums[j],nums[j-h]);}}hh1;//更新h}return nums;}这里增量先选取数组长度一半然后每次缩小一半直至为1 快速排序
快速排序也是一个基于分治的算法 从数组中选取一个中轴元素pivot 把小元素放在pivot左边把大元素放在pivot右边 然后继续对左边和右边进行快速排序 归并排序每次对半排序数组排序好左右数组后再合并成有序数组 快速排序先把左右数组调配出然后对左右数组进行排序 快速排序的分治 也就是说先把元素分成左右两部分后然后再接着对左右两部分继续使用快排
对于[L,R]的数组而言当 LR停止递归
方法一双指针法
这种方法先移动i或者先移动j都可以 class Solution {
public:vectorint sortArray(vectorint nums) {quickSort(nums,0,nums.size()-1);return nums;}
private://数组分成 比基准值小的序列 基准 比基准值大的序列//返回int基准值不参与比较int quickDetail(vectorint nums,int l,int r){//随机选择基准元素并放在nums[l]位置swap(nums[l],nums[rand()%(r-l1)l]);int enums[l];//双指针int il1;int jr;while(1){while(ij nums[i]e) i;while(ij nums[j]e) j--;if(ij) break;swap(nums[i],nums[j--]);}//j停在小的位置swap(nums[l],nums[j]);return j;}//分治void quickSort(vectorint nums,int l,int r){if(lr) return;//注意是大于等于//先划分数组int pquickDetail(nums,l,r);//再对左右两部分进行分治quickSort(nums,l,p-1);quickSort(nums,p1,r);}
};也可以按照符合要求的判断 int quickDetail(vectorint nums,int l,int r){//随机选择基准元素并放在nums[l]位置swap(nums[l],nums[rand()%(r-l1)l]);int enums[l];//双指针int il1;int jr;while(ij){//先j后i也行while(ij nums[j]e) j--;while(ij nums[i]e) i;if(ij)swap(nums[i],nums[j--]);}//j停在小的位置swap(nums[l],nums[j]);return j;}方法二大于跳过
思路i指向小于等于初始值的位置j不断右移 遇到基准值的右移i不动,j右移遇到基准值的把j指向值和第一个基准值的位置交换也就是i后面的第一个元素
----所以i的位置指向的是最后一个基准值 //数组:[l,r]int partition(vectorint nums,int l,int r){swap(nums[l],nums[rand()%(r-l1)l]);int enums[l];int il;for(int ji1;jr;j){if(nums[j]e){//这里可以不带等号swap(nums[j],nums[i]);}}swap(nums[l],nums[i]);return i;}注意等号无所谓可以大于等于跳过也可以只大于就跳过 这种方法存在致命缺陷就是等于元素过多会让左右两部分极度不平衡 方法三三路快排
[l1,lt]维护的是10的部分[gt,r]维护的10的部分从而[lt1,gt-1]维护等于 igt程序停止 1:这是i值10情况交换i值和gt-1位置的值i不变gt-1 2:这是i值10的情况交换该值和lt1的位置的值lt1,i右移 class Solution {
public:vectorint sortArray(vectorint nums) {threeWayQuick(nums,0,nums.size()-1);return nums;}
private:void threeWayQuick(vectorint nums,int l,int r){if(lr) return;//初始化lt,gt使得[l1,lt],[gt,r]为空int ltl;int gtr1;int enums[l];int il1;while(igt){if(nums[i]e){swap(nums[i],nums[--gt]);}else if(nums[i]e){swap(nums[i],nums[lt]);i;}else{//e,直接右移i;}}swap(nums[l],nums[lt]);//分治threeWayQuick(nums,l,lt-1);threeWayQuick(nums,gt,r);}
};这里等于不需要传值所以需要两个值把分治和划分情况写成一个函数 也可以传入pair
pairint,int partition(vectorint nums,int l,int r){int ltl;int gtr1;int enums[l];int il1;while(igt){if(nums[i]e){swap(nums[i],nums[--gt]);}else if(nums[i]e){swap(nums[i],nums[lt]);i;}else{//e,直接右移i;}}swap(nums[l],nums[lt]);return {lt-1,gt};}void threeWayQuick(vectorint nums,int l,int r){if(lr) return;//初始化lt,gt使得[l1,lt],[gt,r]为空auto [k,v]partition(nums,l,r);//分治threeWayQuick(nums,l,k);threeWayQuick(nums,v,r);}算法的稳定性
若经过排序这些相同元素的相对次序保持不变则称这种排序算法是稳定的否则称为不稳定的。 在原序列中A1A2且A1在A2之前经过排序后,A1仍在A2之前。 稳定性意义
要排序的内容是一个具备多个数字属性的复杂对象且原本的初始顺序存在意义需要在二次排序的基础上保持原有排序的意义。 各排序算法的稳定性
1、堆排序、快速排序、希尔排序、选择排序是不稳定的排序算法
2、基数排序、冒泡排序、插入排序、归并排序是稳定的排序算法
非比较类排序
计数排序 简单版—不考虑稳定性 把数组值大小作为count的下标统计频次 然后赋值回给原数组注意i值是大小 void simpleCountSort(vectorint nums){int n nums.size();int sz 0;//数组元素会作为下标计算出数组长度for(auto val:nums){sz max(sz, val);}vectorint count(sz 1);//数组标号从0开始//遍历数组统计次数for(auto val:nums){count[val];}//最后赋回给numsint j 0;for (int i 0; i sz;i){//遍历countif(count[i]!0){while(count[i]--0){nums[j] i;}}}
}考虑稳定性 计算前缀和这样元素为nums[i],则count[nums[i]]-1对应的位置就是存放的正确位置 数组赋值后把对应频次-1 vectorint countSort(vectorint nums){/*初始化count频次数组*///1计算大小int sz 0;for(auto val:nums){sz max(sz, val);}vectorint count(sz 1);/*计算count前缀和*///1:遍历数组for (auto val:nums){count[val];}//2更新前缀for (int i 0; i sz;i){count[i 1] count[i];}/*存放结果*///倒着赋值vectorint res(nums.size());for (int i nums.size() - 1;i0; i--) {res[count[nums[i]] - 1] nums[i];count[nums[i]]--;//别忘了频次-1}return res;
}桶排序了解—BucketSort
在桶排序里的“桶”是指一种数据结构代表一个区间范围用于临时存储排序元素桶排序是一种分布式排序算法将待排序数组元素分到有限数量的桶里每个桶里的数据分别进行排序 按照桶的顺序将元素合并成有序数组。
桶排序的工作原理可以拆分为 3 步
初始化 m 个桶将 n 个元素分配到 m 个桶中对每个桶内的数据分别进行排序这里可以借助任意排序算法按照桶的从大到小的顺序将所有元素合并成有序数组
例子 假设使用的待排序元素整除规则是 nums[i] / 10分别将待排序数组的每个元素分配到每个桶中。 对每个桶内的数据分别进行排序桶内的排序可以借助任意排序算法比如插入排序、快速排序等。 按照桶的从大到小的顺序将所有元素合并成有序数组。 习题颜色分类
75. 颜色分类 采用不稳定的计数排序就行 void countSort(vectorint nums){//只有012,所以key最大2vectorint count(3);//频次统计for(auto val:nums){count[val];}//赋值回去int j0;for(int i0;i2;i){if(count[i]!0){while(count[i]--0){nums[j]i;}}}}排序力扣题
一数组的相对排序
1122. 数组的相对排序
方法一计数排序
用count数组统计arr1的频次然后遍历arr2输出元素最后遍历count输出余下元素 //计数排序vectorint relativeSortArray(vectorint arr1, vectorint arr2) {//先统计arr1的元素频次vectorint count(1001);for(auto val:arr1){count[val];}//先把arr2的元素输出int j0;for(auto val:arr2){while(count[val]--0){arr1[j]val;}}//再把剩余元素输出for(int i0;icount.size();i){while(count[i]--0){arr1[j]i;}}return arr1;}方法二直接比较
其实就是优先输出arr2顺序的元素然后然后比较顺序输出
----先用map记录arr2的次序map[arr2[i]]i,然后进行比较
如果两个元素都在arr2中比较数组次序如果一个元素在arr2中输出这个元素如果都不在arr2中那么正常比较大小 vectorint relativeSortArray(vectorint arr1, vectorint arr2) {//用map记录arr2相对次序mp[arr2[i]]iunordered_mapint,int mp;for(int i0;iarr2.size();i){mp[arr2[i]]i;}//对arr1用自定义比较sort(arr1.begin(),arr1.end(),[](int x,int y)-bool{if(mp.count(x) mp.count(y)){return mp[x]mp[y];}else if(mp.count(x)){return true;//要xy的x}else if(mp.count(y)){return false;//xy}else{return xy;}});return arr1;}当然也可以这样写sort //对arr1用自定义比较sort(arr1.begin(),arr1.end(),[](int x,int y)-bool{if(mp.count(x)){return mp.count(y)?mp[x]mp[y]:true;}else{//x不再return mp.count(y)?false:xy;}});二数组中第k大的元素
215. 数组中的第K个最大元素
方法一堆排序 注意最大值是逆序的第一个最大n-1,… class Solution {
public:int findKthLargest(vectorint nums, int k) {int nnums.size();for(int i(n-2)/2;i0;i--){shiftDown(nums,n,i);}for(int jn-1;j0;j--){swap(nums[0],nums[j]);shiftDown(nums,j,0);}return nums[n-k];//n-1 n-2}
private:void shiftDown(vectorint nums,int n,int m){int enums[m];while(m*21n){int jm*21;//注意if和while别用错了if(j1n nums[j1]nums[j]) j1;if(nums[j]e){nums[m]nums[j];}else{break;}mj;}nums[m]e;}
};方法二快速排序
