算法日记：分治-快排（颜色分类，排序数组，数组中的第k个最大元素 面试题17.14.最小k个数）

🎬 胖咕噜的稞达鸭：个人主页

颜色分类

解法：三指针
将数组中的0，1，2按照顺序排序，不可以使用sort()。
算法：
i从数组索引为0的位置开始遍历，left在数组下标索引为0的位置，right在索引为n-1的位置。
如果i遍历到的数字nums[i]== 0，跟nums[left]的位置交换，与此同时left++;
如果i遍历到的nums[ i ] == 1;则 i ++；
如果i遍历到的nums[ i ] == 2;则交换nums[ right ]和nums[i ],于此同时right--。
循环的结束条件是i 跟right相遇。
将一段数组分成三份，依次存储0，1，2，用left，right，i分段将数组分为4段。

[0,left]:全部都是0 [left+1,i-1]:全部都是1 [i,right-1]:待扫描的元素 [right,n-1]:全部都是2

classSolution{public:voidsortColors(vector<int>&nums){intleft=-1,right=nums.size();//left设置为1的位置上：初始还没有找到0的位置，right设置为nums.size()的位置初始化还没有找到2的位置inti=0;while(i<right){if(nums[i]==0)swap(nums[++left],nums[i++]);elseif(nums[i]==1)i++;elseswap(nums[--right],nums[i]);//i不用++，不然交换过去的i是的还没有被处理的，而不是2}}};

912.排序数组

[912. 排序数组 - 力扣（LeetCode）](排序数组)

解法一：快速排序

classSolution{public:vector<int>sortArray(vector<int>&nums){srand(time(NULL));//种下一颗随机数的种子qsort(nums,0,nums.size()-1);returnnums;}//快排voidqsort(vector<int>&nums,intl,intr){if(l>=r)return;//数组分类intkey=getRandom(nums,l,r);inti=l,left=l-1,right=r+1;while(i<right){if(nums[i]<key)swap(nums[++left],nums[i++]);elseif(nums[i]==key)i++;elseswap(nums[--right],nums[i]);}//数组分为三块[l,left][left+1,right - 1][right,r]qsort(nums,l,left);qsort(nums,right,r);}intgetRandom(vector<int>&nums,intleft,intright){intr=rand();returnnums[r%(right-left+1)+left];}};

解法二：归并排序
将数组划分为两块，两块数组都有序之后合并到一起，找两个指针，ptr1,ptr2。分别遍历这两个数组，ptr1从数组1开始，int ptr1 = left;ptr2从数组2开始，int ptr2 = mid + 1;哪个在指向数字的过程中遇到的数小就插入，随后要处理未完成的数组，数组1有余留就插入到tmp中，数组2同理。
最后按照顺序返回排好序的数组。

classSolution{vector<int>tmp;public:vector<int>sortArray(vector<int>&nums){tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);returnnums;}voidmergeSort(vector<int>&nums,intleft,intright){if(left>=right)return;//1.选择中间点划分区间intmid=(right+left)>>1;//相加之后右移一位//2，把左右区间排序mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);//3.合并两个有序数组intptr1=left,ptr2=mid+1,i=0;while(ptr1<=mid&&ptr2<=right){tmp[i++]=nums[ptr1]<=nums[ptr2]?nums[ptr1++]:nums[ptr2++];}//4.处理未完成的数组while(ptr1<=mid)tmp[i++]=nums[ptr1++];while(ptr2<=right)tmp[i++]=nums[ptr2++];//5.还原for(inti=left;i<=right;i++)nums[i]=tmp[i-left];}};

数组中的第k个最大元素

[215. 数组中的第K个最大元素 - 力扣（LeetCode）](数组中的第k个最大元素)

判断逻辑：

1. 如果前c个最大的元素已经包含了第k大 → 去大于区找
2. 如果前(c+b)个最大的元素包含了第k大 → 第k大就是key
3. 否则 → 去小于区找（调整k的值）

具体示例分析

示例1：找第2大

数组：[5, 3, 7, 3, 1, 3, 9] k=2 三路划分后：小于区[1], 等于区[3,3,3], 大于区[9,7,5] c=3, b=3 判断： 1. c=3 >= k=2 ✓ → 第2大在大于区 2. 在大于区[9,7,5]中找第2大 → 返回7

示例2：找第4大

数组：[5, 3, 7, 3, 1, 3, 9] k=4 三路划分后：小于区[1], 等于区[3,3,3], 大于区[9,7,5] c=3, b=3 判断： 1. c=3 >= k=4? ✗ 2. b+c=6 >= k=4? ✓ → 第4大在等于区，返回key=3

示例3：找第7大（最小）

数组：[5, 3, 7, 3, 1, 3, 9] k=7 三路划分后：小于区[1], 等于区[3,3,3], 大于区[9,7,5] c=3, b=3 判断： 1. c=3 >= k=7? ✗ 2. b+c=6 >= k=7? ✗ 3. 第3种情况 → 在小于区[1]找第(k-b-c)=7-6=1大 返回1

classSolution{public:intfindKthLargest(vector<int>&nums,intk){//种一棵随机数种子srand(time(NULL));//随机树种子returnqsort(nums,0,nums.size()-1,k);}intgetRandom(vector<int>&nums,intleft,intright){intr=rand();returnnums[r%(right-left+1)+left];}intqsort(vector<int>&nums,intl,intr,intk){if(l==r)returnnums[l];//如果数组中l和r是相等的，不用进行下面的操作了，直接返回//1.随机选择基准元素intkey=getRandom(nums,l,r);//在l,r这段区间随机返回一个随机数//2.随机选择基准元素将数组分为3组:[l,left][left-1,right+1][right,r]inti=l,left=l-1,right=r+1;while(i<right){if(nums[i]<key)swap(nums[++left],nums[i++]);elseif(nums[i]==key)i++;elseswap(nums[--right],nums[i]);}//3.分情况讨论intc=r-right+1;//第三组元素的数量intb=right-left-1;//第二组元素的数量if(c>=k)returnqsort(nums,right,r,k);elseif(b+c>=k)returnkey;elsereturnqsort(nums,l,left,k-b-c);}};

面试题17.14.最小K个数

[面试题 17.14. 最小K个数 - 力扣（LeetCode）](最小K个数)

解法：随机数作为基准元素 + 数组分为三段

--------------------------- | | | | l left right r [l,left]:<key的元素 [left,right]:==key的元素 [right,r]:>key的元素

返回数组中最小的K个数，首先要从[l,left]中寻找，
假设【l,left】中有a个数字，int a = left - l + 1;
假设【left,right】中有b个数字，int b = right - left - 1;
如果要找的k的个数小于a,就在a区间中寻找；
如果要找的k的个数小于a + b这一大个区间，返回key；
实在找不到可以在剩下的k - a- b个数字中（也就是大于key）的区间中找。

classSolution{public:vector<int>smallestK(vector<int>&arr,intk){srand(time(NULL));qsort(arr,0,arr.size()-1,k);return{arr.begin(),arr.begin()+k};//最后返回的是一个数组}voidqsort(vector<int>&arr,intl,intr,intk){if(l>=r)return;inti=l,left=l-1,right=r+1;intkey=getRandom(arr,l,r);while(i<right){if(arr[i]<key)swap(arr[i++],arr[++left]);elseif(arr[i]==key)i++;elseswap(arr[i],arr[--right]);}//分情况讨论inta=left-l+1;intb=right-left-1;if(a>k)returnqsort(arr,l,left,k);elseif(a+b>=k)return;elsereturnqsort(arr,right,r,k-a-b);}intgetRandom(vector<int>&arr,intleft,intright){intr=rand();returnarr[r%(right-left+1)+left];}};

遇到分区/选择类算法题的通用解法思路

核心模式识别
当你看到以下特征时，考虑使用分区/选择算法：

1. 需要重新排序数组元素（如按颜色、值排序）
2. 寻找第K大/第K小的元素
3. 寻找前K个最小/最大的元素
4. 题目要求O(n)时间复杂度或禁止使用sort()

四步解题框架
第一步：分析问题类型

如果是排序/分类→ 直接用三指针分区（如颜色分类）
如果是第K个元素 → 用快速选择
如果是前K个元素 → 用改进的快速选择

第二步：选择分区策略

// 三路分区模板（最常用）intleft=l-1,right=r+1;// 扩展边界inti=l;// 当前指针intkey=getRandom(nums,l,r);// 随机基准值while(i<right){if(nums[i]<key)swap(nums[++left],nums[i++]);elseif(nums[i]==key)i++;elseswap(nums[--right],nums[i]);}// 分区结果：// [l, left] < key// [left+1, right-1] == key// [right, r] > key

第三步：判断递归方向
cpp

// 对于第K大元素：intlessCount=left-l+1;// 小于区的数量intequalCount=right-left-1;// 等于区的数量intgreaterCount=r-right+1;// 大于区的数量// 判断逻辑：if(greaterCount>=k){// 在大于区找第k大returnqsort(nums,right,r,k);}elseif(greaterCount+equalCount>=k){// 第k大在等于区returnkey;}else{// 在小于区找第(k - greaterCount - equalCount)大returnqsort(nums,l,left,k-greaterCount-equalCount);}

第四步：边界处理

// 递归终止条件if(l>=r)returnnums[l];// 第K大元素if(l>=r)return;// 排序/分类if(k==0)return{};// 前K个元素

实战决策树

问题类型 ├── 重新排序/分类（如颜色分类） │ ├── 固定规则（如0,1,2）→ 三指针遍历交换 │ └── 任意规则 → 三路分区 ├── 寻找单个元素（第K大/小） │ ├── 第K大 → 按大于区、等于区、小于区顺序判断 │ └── 第K小 → 按小于区、等于区、大于区顺序判断 └── 寻找多个元素（最小/大的K个数） ├── K个数需要排序 → 先快速选择，再对前K个排序 └── K个数无需排序 → 直接分区到正确位置

关键技巧提醒
随机化基准值是避免最坏情况的关键

srand(time(NULL));// 随机种子intr=rand();returnnums[r%(right-left+1)+left];

指针边界处理

初始时让 left=l-1, right=r+1

这样分区后区间更清晰

i指针的处理

交换到左边的元素可以 i++（已处理） 交换到右边的元素不要 i++（需要重新处理）

复杂度分析

平均：O(n) 或 O(n log n)
最坏：O(n²) → 通过随机化避免

常见易错点
错误 正确做法
忘记处理相等情况 一定要有else if(nums[i]==key)i++
交换后错误移动指针 从左换来的可以i++，从右换来的不能i++
递归方向判断错误 画图明确各分区的元素数量
边界条件漏掉 总是检查 if(l>=r)

一句话总结

“随机基准三路分，数量判断定区间，递归缩小范围找”——遇到这类问题，先随机选基准值，三路分区，根据各区间元素数量决定下一步操作，递归缩小范围直到找到答案。