重庆市建设工程施工安全信息网,韩国seocaso,wordpress文章列表 框,网站开发合同违约责任文章目录 1、颜色分类2、排序数组3、第k个最大的元素#xff08;快速选择#xff09;4、最小的k个数#xff08;快速选择#xff09; 分治#xff0c;就是分而治之#xff0c;把大问题划分成多个小问题#xff0c;小问题再划分成更小的问题。像快排和归并排序就是分治思… 文章目录 1、颜色分类2、排序数组3、第k个最大的元素快速选择4、最小的k个数快速选择 分治就是分而治之把大问题划分成多个小问题小问题再划分成更小的问题。像快排和归并排序就是分治思想。分治需要把数据分成几个区间分区间则要通过基准值来划分 1、颜色分类
颜色分类 其实这道题的做法是三指针。双指针思路中定义两个指针假设要把整个数组划分成a和b区间ab区间的数有各自的特点一个指针遍历整个数组另一个指针指向a区间的最后一个元素位置。而三指针也是同样的思路三个指针abc三个区间一个指针仍然在遍历数组但它不需要遍历完所有一个指针指向a区间的最右侧一个指针指向c区间的最左侧这样三个区间也就能划分出来了。在实际操作中会分出四个区间 [0, left]全是0[left 1, i - 1]全是1[i, right - 1]是待扫描的元素[right, n - 1]全是2。
代码开始时我们要如何做left和right自然是在整个数组下标的0和n - 1处i每次检测到数字就去判断应该放到哪个区间然后交换元素把数字放到区间left或者right移动而i如果是放到left左边i可以但是和right右边的元素交换后i不能它还需要判断交换过来的数字。 void sortColors(vectorint nums) {int n nums.size();int i 0, left -1, right n;//为什么要这么设置left和right1的值? 看下面的代码就能明白了while(i right)//为什么要小于rightright到最后都是为2的元素等到i和right重合时其实就已经完成了整体的排序{if(nums[i] 0){swap(nums[left], nums[i]);}else if(nums[i] 1){i;}else if(nums[i] 2){swap(nums[--right], nums[i]);}}}2、排序数组
排序数组 其实这道题就是实现快排。我们要设置基准值key把区间划分成两部分key 和 key然后再到两个区间实现同样的操作找key划分区间。如果数组里都是重复元素的话这个排序的复杂度就不好了。那么这里就把数组分三块的思想来实现快排其实这个数组分三块的思路就是排序2那篇博客中的双指针法思路都相似。我们要分成三个区间 key key key每次比较的时候就是交换指针等操作。
同上面一样 小于keyswapnums[left], nums[i] 等于keyi 大于keyswapnus[–right], nums[i] 但是这里还有优化上面时间复杂度是O(N)想要达成N * logN就必须要随机选取key值。而这里的随机也不是简单的随机我们要让整个区间的数都能等概率地没取到我们的做法就是rand() % (right - left 1) left偏移量 left得到对应的数值这个得出来的值是数组的下标也就是nums[rand() % (right - left 1) left]。
上代码 vectorint sortArray(vectorint nums) {srand(time(NULL));//开始随机种下随机数种子qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vectorint nums, int l, int r){if(l r) return ;//数组分三块int key getRandom(nums, l, r);int i l, left l - 1, right r 1;//这里就和上面的颜色分类的做法就一样了也就是上面灰框中的实现while(i right){if(nums[i] key) swap(nums[left], nums[i]);else if(nums[i] key) i;else swap(nums[--right], nums[i]);}qsort(nums, l, left);qsort(nums, right, r);}int getRandom(vectorint nums, int left, int right){int r rand();return nums[r % (right - left 1) left];}3、第k个最大的元素快速选择
数组中的第K个最大元素 TOP K有4种问题第k大第k小前k大前k小。之前的博客对此用的是堆排序的算法。还有另外一个就是快速选择算法。堆排是O(N*logN)而快速选择是O(N)。
快速选择基于快排。整个区间左右端点为l和r分成三个区间abc三个区间内我们需要确定第k大的数字在哪个区间内。假设abc就是每个区间的元素个数如果在第三个区间也就是key的区间那么c k如果第一个条件不成立那么如果在第二区间那么b c k直接返回key就行因为第二个区间都是key的数字如果上面两个条件都不成立那么就去第一个区间找找k - (b c)大的数字。 int findKthLargest(vectorint nums, int k) {/*priority_queueint, vectorint, greaterint pq(nums.begin(), nums.begin() k);for(size_t i k; i nums.size(); i){if(nums[i] pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();*///上面是用优先级队列解决的srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}int qsort(vectorint nums, int l, int r, int k){if(l r) return nums[l];//必然存在至少一个元素所以l不可能大于r//1. 随机选择基准元素int key getRandom(nums, l, r);//2. 根据基准元素分三块int left l - 1, right r 1, i l;while(i right){if(nums[i] key) swap(nums[left], nums[i]);else if(nums[i] key) i;else swap(nums[--right], nums[i]);}int c r - right 1;int b right - left - 1;if(c k) return qsort(nums, right, r, k);else if(b c k) return key;else return qsort(nums, l, left, k - b - c);}int getRandom(vectorint nums, int left, int right){return [rand() % (right - left 1) left];}4、最小的k个数快速选择
剑指 Offer 40. 最小的k个数 针对这样的问题我们可以堆排序也可以快速选择算法。堆排是N * logk快速选择可以到达N。
还是l left right rabc。如果a k那就在a区间找条件不符合那就去a b k那就返回key因为第一个条件不符合那么第二个条件符合的话k一定就是在key的区间那就返回key上述两种条件都不符合那就得在c区间找。
对上一个稍作修改。 vectorint getLeastNumbers(vectorint arr, int k) {srand(time(NULL));qsort(arr, 0, arr.size() - 1, k);return {arr.begin(), arr.begin() k};}void qsort(vectorint nums, int l, int r, int k){if(l r) return ;int key getRandom(nums, l, r);int left l - 1, right r 1, i l;while(i right){if(nums[i] key) swap(nums[left], nums[i]);else if(nums[i] key) i;else swap(nums[--right], nums[i]);}int a left - l 1;int b right - left - 1;if(a k) return qsort(nums, l, left, k);else if(b a k) return ;else qsort(nums, right, r, k - b - a);}int getRandom(vectorint nums, int left, int right){return nums[rand() % (right - left 1) left];}结束。 文章转载自： http://www.morning.lkfhk.cn.gov.cn.lkfhk.cn http://www.morning.kscwt.cn.gov.cn.kscwt.cn http://www.morning.xlbtz.cn.gov.cn.xlbtz.cn http://www.morning.krywy.cn.gov.cn.krywy.cn http://www.morning.rxcqt.cn.gov.cn.rxcqt.cn http://www.morning.pgmyn.cn.gov.cn.pgmyn.cn http://www.morning.jksgy.cn.gov.cn.jksgy.cn http://www.morning.jpgfx.cn.gov.cn.jpgfx.cn http://www.morning.bpmdn.cn.gov.cn.bpmdn.cn http://www.morning.wyctq.cn.gov.cn.wyctq.cn http://www.morning.hymmq.cn.gov.cn.hymmq.cn http://www.morning.xckqs.cn.gov.cn.xckqs.cn http://www.morning.dzqyn.cn.gov.cn.dzqyn.cn http://www.morning.xrlwr.cn.gov.cn.xrlwr.cn http://www.morning.pnjsl.cn.gov.cn.pnjsl.cn http://www.morning.cldgh.cn.gov.cn.cldgh.cn http://www.morning.stsnf.cn.gov.cn.stsnf.cn http://www.morning.pwwjs.cn.gov.cn.pwwjs.cn http://www.morning.zpfr.cn.gov.cn.zpfr.cn http://www.morning.sqqds.cn.gov.cn.sqqds.cn http://www.morning.ggjlm.cn.gov.cn.ggjlm.cn http://www.morning.tqygx.cn.gov.cn.tqygx.cn http://www.morning.mjzgg.cn.gov.cn.mjzgg.cn http://www.morning.smygl.cn.gov.cn.smygl.cn http://www.morning.brkc.cn.gov.cn.brkc.cn http://www.morning.chzqy.cn.gov.cn.chzqy.cn http://www.morning.brtxg.cn.gov.cn.brtxg.cn http://www.morning.dwhnb.cn.gov.cn.dwhnb.cn http://www.morning.jncxr.cn.gov.cn.jncxr.cn http://www.morning.xsfg.cn.gov.cn.xsfg.cn http://www.morning.kryn.cn.gov.cn.kryn.cn http://www.morning.wmmqf.cn.gov.cn.wmmqf.cn http://www.morning.rsfp.cn.gov.cn.rsfp.cn http://www.morning.hdqqr.cn.gov.cn.hdqqr.cn http://www.morning.cnhgc.cn.gov.cn.cnhgc.cn http://www.morning.jcfqg.cn.gov.cn.jcfqg.cn http://www.morning.lwygd.cn.gov.cn.lwygd.cn http://www.morning.tzzfy.cn.gov.cn.tzzfy.cn http://www.morning.flfdm.cn.gov.cn.flfdm.cn http://www.morning.krhkn.cn.gov.cn.krhkn.cn http://www.morning.wfjyn.cn.gov.cn.wfjyn.cn http://www.morning.jfbrt.cn.gov.cn.jfbrt.cn http://www.morning.lzqtn.cn.gov.cn.lzqtn.cn http://www.morning.ksjnl.cn.gov.cn.ksjnl.cn http://www.morning.hgfxg.cn.gov.cn.hgfxg.cn http://www.morning.pwksz.cn.gov.cn.pwksz.cn http://www.morning.wchsx.cn.gov.cn.wchsx.cn http://www.morning.fgppj.cn.gov.cn.fgppj.cn http://www.morning.ngmjn.cn.gov.cn.ngmjn.cn http://www.morning.skkln.cn.gov.cn.skkln.cn http://www.morning.fktlr.cn.gov.cn.fktlr.cn http://www.morning.wcczg.cn.gov.cn.wcczg.cn http://www.morning.mcjyair.com.gov.cn.mcjyair.com http://www.morning.wnjsp.cn.gov.cn.wnjsp.cn http://www.morning.xhlpn.cn.gov.cn.xhlpn.cn http://www.morning.deanzhu.com.gov.cn.deanzhu.com http://www.morning.fjgwg.cn.gov.cn.fjgwg.cn http://www.morning.pfmsh.cn.gov.cn.pfmsh.cn http://www.morning.jqmmf.cn.gov.cn.jqmmf.cn http://www.morning.rlbfp.cn.gov.cn.rlbfp.cn http://www.morning.ssmhn.cn.gov.cn.ssmhn.cn http://www.morning.yrjkp.cn.gov.cn.yrjkp.cn http://www.morning.qsxxl.cn.gov.cn.qsxxl.cn http://www.morning.rtsd.cn.gov.cn.rtsd.cn http://www.morning.xtkw.cn.gov.cn.xtkw.cn http://www.morning.chehb.com.gov.cn.chehb.com http://www.morning.rjxwq.cn.gov.cn.rjxwq.cn http://www.morning.kflzy.cn.gov.cn.kflzy.cn http://www.morning.nbqwt.cn.gov.cn.nbqwt.cn http://www.morning.muniubangcaishui.cn.gov.cn.muniubangcaishui.cn http://www.morning.gtylt.cn.gov.cn.gtylt.cn http://www.morning.nldsd.cn.gov.cn.nldsd.cn http://www.morning.mpngp.cn.gov.cn.mpngp.cn http://www.morning.ghrhb.cn.gov.cn.ghrhb.cn http://www.morning.qtyfb.cn.gov.cn.qtyfb.cn http://www.morning.yrfxb.cn.gov.cn.yrfxb.cn http://www.morning.cbtn.cn.gov.cn.cbtn.cn http://www.morning.tztgq.cn.gov.cn.tztgq.cn http://www.morning.ptmch.com.gov.cn.ptmch.com http://www.morning.xpqsk.cn.gov.cn.xpqsk.cn
