首页/新闻资讯/正文详情

优选算法专题7:分治

发布时间:2026/11/19 3:50:24 来源:云帆数科 栏目:资讯中心
优选算法专题7:分治
分治目录分治试题1颜色分类算法原理代码编写试题2排序数组快排算法原理代码编写试题3数组中的第K个最大元素算法原理代码编写试题4最小的k个数算法原理代码编写试题5排序数组归并算法原理代码编写试题6数组中的逆序对算法原理代码编写试题7计算右侧小于当前元素的个数算法原理代码编写试题8翻转对算法原理代码编写试题1颜色分类算法原理分治分而治之解法三指针代码编写个人版本class Solution { public: void sortColors(vectorint nums) { int left -1, right nums.size(), i 0; while(i right) { if(nums[i] 0) { swap(nums[left], nums[i]); } else if(nums[i] 1) { i; } else { swap(nums[--right], nums[i]); } } } };标准版本class Solution { public: void sortColors(vectorint nums) { int n nums.size(); int left -1, right n, i 0; while(i right) { if(nums[i] 0) swap(nums[left], nums[i]); else if(nums[i] 1) i; else swap(nums[--right],nums[i]); } } };试题2排序数组快排算法原理解法快速排序代码编写class Solution { public: 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]); } } //[1,left][left 1,right - 1][right,r] 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个最大元素算法原理解法一堆排序O(NlogN)解法二快速选择算法O(N)代码编写class Solution { public: int findKthLargest(vectorint nums, int k) { 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]; } //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]); } } //3. 分情况讨论 int c r - right 1; int b ( right - 1 ) - ( left 1 ) 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 nums[rand() % (right - left 1) left]; } };试题4最小的k个数算法原理解法一排序O(NlogN)解法二大根堆O(NlogK)解法三快速选择算法O(N)随机选择基准元素数组分三块代码编写class Solution { public: vectorint inventoryManagement(vectorint nums, int k) { srand(time(NULL)); qsort(nums, 0, nums.size() - 1, k); return {nums.begin(), nums.begin() k}; } void qsort(vectorint nums, int l,int r,int k) { if(l r) { return; } //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]); } } // [l,left][left1,right-1][right,r] int a left - l 1; int b right - left - 1; if(a k) { qsort(nums, l, left, k); } else if(a b k) { return; } else { qsort(nums, right, r, k - a - b); } } int getRandom(vectorint nums, int l,int r) { return nums[rand() % (r - l 1) l]; } };试题5排序数组归并算法原理代码编写class Solution { vectorint tmp; public: vectorint sortArray(vectorint nums) { tmp.resize(nums.size()); mergeSort(nums, 0, nums.size() - 1); return nums; } void mergeSort(vectorint 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[cur1] : nums[cur2]; } //4. 处理没有遍历完的数组 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]; } } };试题6数组中的逆序对算法原理解法一暴力枚举两层for循环解法二归并排序代码编写class Solution { int tmp[50010]; public: int reversePairs(vectorint nums) { return mergeSort(nums, 0, nums.size() - 1); } int mergeSort(vectorint 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]; } } //4. 处理剩余排序 while(cur1 mid) { tmp[i] nums[cur1]; } while(cur2 right) { tmp[i] nums[cur2]; } //5. 还原 for(int j left; j right; j) { nums[j] tmp[j - left]; } return ret; } };试题7计算右侧小于当前元素的个数算法原理代码编写class Solution { vectorint ret; vectorint index; int tmpNums[500010]; int tmpIndex[500010]; public: vectorint countSmaller(vectorint 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(vectorint nums, int left, int right) { if(left right) { return; } //1. 根据中间元素划分区间 int mid (right left) 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]; } } //4. 处理剩下排序 while(cur1 mid) { tmpNums[i] nums[cur1]; tmpIndex[i] index[cur1]; } while(cur2 right) { tmpNums[i] nums[cur2]; tmpIndex[i] index[cur2]; } //5. 还原 for(int j left; j right; j) { nums[j] tmpNums[j - left]; index[j] tmpIndex[j - left]; } } };试题8翻转对算法原理解法一暴力枚举解法二分治代码编写降序策略class Solution { int tmp[50010]; public: int reversePairs(vectorint nums) { return mergeSort(nums, 0, nums.size() - 1); } int mergeSort(vectorint nums, int left, int right) { if(left right) { return 0; } int ret 0; //1. 找中间点划分区间 int mid (left right) 1; //2. 计算左右两侧翻转对 ret mergeSort(nums, left, mid); ret mergeSort(nums,mid 1, right); //3. 计算一左一右翻转对数量 int cur1 left, cur2 mid 1, i left; while(cur1 mid) { while(cur2 right nums[cur2] nums[cur1] / 2.0) { 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]; } //5. 还原 for(int j left; j right; j) { nums[j] tmp[j]; } return ret; } };升序策略class Solution { int tmp[50010]; public: int reversePairs(vectorint nums) { return mergeSort(nums, 0, nums.size() - 1); } int mergeSort(vectorint nums, int left, int right) { if(left right) { return 0; } int ret 0; //1. 找中间点划分区间 int mid (left right) 1; //2. 计算左右两侧翻转对 ret mergeSort(nums, left, mid); ret mergeSort(nums,mid 1, right); //3. 计算一左一右翻转对数量 int cur1 left, cur2 mid 1, i left; while(cur2 right) { while(cur1 mid nums[cur2] nums[cur1] / 2.0) { 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]; } //5. 还原 for(int j left; j right; j) { nums[j] tmp[j]; } return ret; } };

相关推荐

openclaw(小龙虾)
openclaw(小龙虾)

openclaw(小龙虾) 一、什么是openclaw openclaw是一个可以执行具体任务的AI智能体,让AI不仅仅停留在问答阶段,能真正帮助我们处理一些事情。 注意:小龙虾存在安全风险,请使用私人电脑进行操作。 需要nodejs… · 2026/9/15 7:30:54

PM项目管理-权利利益模型
PM项目管理-权利利益模型

· 2026/9/20 22:08:39

vivado报错及解决【十】
vivado报错及解决【十】

ERROR: [Synth 8-1766] cannot open include file include.v这个错误是我们在引用类似以下的参数文件时,vivado系统找不到文件导致的。include "params.v"AMD官方的解决方案如下:AMD官方论坛提供了两种解决方案:1.将include.v文件设… · 2026/9/10 8:30:36

平凉电工证通过率千万别踩坑,工地太忙根本没时间复习考试
平凉电工证通过率千万别踩坑,工地太忙根本没时间复习考试

平凉电工证通过率千万别踩坑,工地太忙根本没时间复习考试 工地太忙根本没时间复习考试,这几乎是每个电工从业者最真实的心声。尤其是在平凉这样的地区,工地节奏快、工期紧,很多人一拿到电工证就想着赶紧上岗,根本没心思去花时间复习。可偏偏电工证的… · 2026/11/19 3:49:42

茂名年审电工证千万别踩坑,怕考不过白交培训费怎么办
茂名年审电工证千万别踩坑,怕考不过白交培训费怎么办

茂名年审电工证千万别踩坑,怕考不过白交培训费怎么办 怕考不过白交培训费?你不是一个人。茂名年审电工证考试,确实是很多电工从业者的“生死关”。尤其是在当前建筑、电力行业中,电工证已经成为入行和晋升的“硬门槛”,但一不小心就容易掉进培训班的“陷… · 2026/11/19 3:49:42

电工证复审不合理?别让含金量被流程拖垮
电工证复审不合理?别让含金量被流程拖垮

电工证复审不合理?别让含金量被流程拖垮 怕考不过白交培训费?电工证复审不合理的问题确实让不少学员头疼。尤其是从事济源公路工程行业的朋友,对电工证的含金量格外看重。可现实中,复审流程复杂、审核严格、甚至出现“不合理”扣分或直接不通过的情况,让… · 2026/11/19 3:49:42

上虞电工证办理别乱找!内部消息教你避坑
上虞电工证办理别乱找!内部消息教你避坑

上虞电工证办理别乱找!内部消息教你避坑 你是不是也和很多在上虞的电工一样,想考个电工证,却不知道去哪里报名?怕被中介骗钱,怕报名流程复杂,怕考试内容看不懂?这些我都懂,因为我自己也经历过。今天这波 内部消息 ,就是给你讲讲怎么在… · 2026/11/19 3:49:42

电工证上哪报名通过率揭秘:工地太忙根本没时间复习考试
电工证上哪报名通过率揭秘:工地太忙根本没时间复习考试

电工证上哪报名通过率揭秘:工地太忙根本没时间复习考试 工地太忙根本没时间复习考试,这是很多一线电工的共同痛点。特别是对于刚入职的新人,像我这样在驻马店做工地电工的,每天从早忙到晚,连吃饭都得掐着时间点。可偏偏到了要考电工证的时候,时间不够用… · 2026/11/19 3:49:42

低压电工证年审照片怎么拍?外省证能不能转过来?全国通用不迷路
低压电工证年审照片怎么拍?外省证能不能转过来?全国通用不迷路

低压电工证年审照片怎么拍?外省证能不能转过来?全国通用不迷路 之前考的证在外省能不能转过来?这个问题是很多人第一次听说低压电工证的时候就会问的。其实, 低压电工证是全国通用的… · 2026/11/19 3:48:42

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/18 8:19:55

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/18 8:19:53

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/18 14:38:14

姑苏区哪里考电工证好考前押题怎么找
姑苏区哪里考电工证好考前押题怎么找

姑苏区哪里考电工证好考前押题怎么找 工地太忙根本没时间复习考试,电工证考前还总找不到靠谱的 考前押题 资源,真让人头疼。如果你也是在苏州姑苏区从事建筑或电力行业的,那这些建议你一定要看完。 为什么姑苏区考电工证的人这么多?… · 2026/11/19 0:00:12

罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南
罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南

罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南 之前考的证在外省能不能转过来?这几乎是每个特种作业证书持有者都会遇到的问题,特别是像你这样已经在外地工作多年,想回老家罗定发展或者重新规划职业路径的人。别急,今天就给你一条清晰的路… · 2026/11/19 0:00:12

罗定能考电工证吗 电工证含金量到底有多少?
罗定能考电工证吗 电工证含金量到底有多少?

罗定能考电工证吗 电工证含金量到底有多少? 之前考的证在外省能不能转过来,这几乎是每个准备考电工证的朋友最先想到的问题。特别是在罗定这样的地方,很多人的电工证都是在外地考的,现在想在当地继续使用,但不知道怎么办。实际上,电工证的 含金量… · 2026/11/19 0:00:12

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 0:22:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码