深度解析之算法之分治（快排）

44.颜色分类

题目链接
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入： nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入： nums = [2,0,1]
输出： [0,1,2]

就是给这三类进行排序

解法：三指针
i这个指针遍历数组
left指针标记0区域最右侧
right标记2区域的最左侧
那么此时我们的数组就被划分为四个部分了

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

如果我们此时的nums[i]=0的话，那么我们将当前位置的0和nums[left+1]位置的数进行交换操作，

但是如果我们此时i的位置就是left+1的话，那么我们将left和left+1的位置进行交换操作，但是我们交换后我们的left还是要往后面移动，不如我们先让left先进行++操作
我们更换下代码的思路，如果我们当前的nums[i]=0的话，我们直接将nums[++left]和nums[i++]进行交换，我们先将left++和i的位置交换，交换完成之后我们的i再往后面进行移动的操作

如果我们的nums[i]=1的话，那么我们直接将i++就行了，因为我们此时的[left+1,i-1]范围内都是1

如果我们此时的nums[i]=2的话，我们将此时的位置和right-1进行交换操作
代码的话我们可以先让right–，然后再将我们和我们i位置的交换，这样我们的指针也进行了移动的操作，此时我们将原先right-1的位置和i位置的元素进行交换了，那么我们此时的i位置的元素还是带扫描的元素，因为我们将后面的元素挪动到前面来了，我们此时是不需要动i的

思路如下

当我们i和right相遇之后，我们的带扫描的元素都扫描完成了

class Solution { public:     void sortColors(vector<int>& nums)     {         int n =nums.size();         //三个指针         int left=-1,right=n,i=0;         while(i<right)//当我们的i和right相遇之后的话循环就结束了         {             if(nums[i]==0)swap(nums[++left],nums[i++]);             else if(nums[i]==1) i++;             else swap(nums[--right],nums[i]);         }     } }; 

45.快速排序

题目链接
给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

输入： nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入： nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

用数组分三块的思想，实现快排
左边的区域是小于key的，中间的是等于key的，右边的是大于key的，和我们上面的颜色分类是一样的

当我们的nums[i]<key的话，那么我们需要将nums[++left]位置和num[i+1]的位置进行交换

如果等于k的话，那么就是i++

如果大于k的话，那么就是交换nums[–right]和nums[i]进行交换的，这里交换完成之后我们是 不需要进行i++的，因为这种情况交换后的i++

优化：使用随机的方式选择基准元素，这样可以让我们的时间复杂度接近于nlon N
等概率的返回区间上任意一个数字

我们让r=rand()
r%(right-left+1)+left
我们的r%(right-left+1)的范围就是[o,n-1]
然后我们加上一个left得到的就是一个随机值了

我们这里的这个是一个随机的下标
所以我们的基准元素就是nums[r%(right-left+1)+left]

class Solution { public:     vector<int> sortArray(vector<int>& nums)     {         srand(time(NULL));//种下一个随机数种子         qsort(nums,0,nums.size()-1);//将数组、左指针和右指针的下标传过去         return nums;     }     //快排     void qsort(vector<int>&nums,int l,int r)     {         if(l>=r) return ;//要么你的区间是只有一个元素，要么就是区间不存在的         //数组分三块         int key=getRandom(nums,l,r);//getRandom可以根据数组和左区间右区间进行随机数的获取操作         //进行三个指针的初始化操作         int i=l,left=l-1,right=r+1;//left从区间的最左侧开始，right从区间的最右侧开始         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] [left+1,right-1]  [right,r]         qsort(nums,l,left);         qsort(nums,right,r);         //通过递归，我们能够将每个子数组进一步分割，直到它们只有一个元素为止，这时数组已经是有序的。     }     int getRandom(vector<int>&nums,int left,int right)     {         int r=rand();         return nums[r%(right-left+1)+left];     } }; 

选择一个基准元素（pivot），将数组划分为两部分，使得左边部分的所有元素都小于等于基准元素，右边部分的所有元素都大于等于基准元素。

递归地对左右两部分子数组分别进行快速排序。

由于在分解过程中，元素已经被放置在正确的相对位置上，因此不需要额外的合并操作，最终整个数组就会被排序好。

函数内部首先选择一个基准元素，然后将数组划分为三个部分，接着递归地对左右两部分子数组进行排序

46.数组中的第K个最大元素

题目链接
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入:[3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入:[3,2,3,1,2,4,5,5,6], k = 4
输出: 4

我们之前使用优先级队列进行问题解决

class Solution { public:     int findKthLargest(vector<int>& nums, int k)     {         //将数组中的元素先放入到优先级队列中,默认是大堆         priority_queue<int> p(nums.begin(),nums.end());         //我们删除k-1次，那么循环结束的时候的堆顶的数据就是当前最大了的，我们直接返回堆顶数据就行了         while(--k)//--k是走k-1次,k--是走k次         {             p.pop();         }         return p.top();     } }; 

这里我们将元素放到优先级队列中，默认是大堆，我们从数组的位置开始放，然后第k个最大的数字就在我们的堆顶了，然后我们循环进行删除堆顶数据，循环k-1次，最后得到的就是我们的堆顶的数据

但是这里的话我们使用分治的方法，基于快排而实现的选择算法

数组分三块+随机选择基准元素

如果我们的第k大落在了>key的区间上，那么我们左边的区间就不用去找了

class Solution { public:     int findKthLargest(vector<int>& nums, int k)     {         srand(time(NULL));//种一个随机数的种子         return qsort(nums,0,nums.size()-1,k);//直接利用qsort返回最终的结果就行了     }     int qsort(vector<int>&nums,int l,int r,int k)     {         if(l==r) return nums[l];//如果区间只有一个元素的话，那么我们直接返回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;//[right,r]这个区间的元素的个数         int b=right-1-(left+1)+1;//[left+1,right-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(vector<int>&nums,int left,int right)     {         return nums[rand()%(right-left)+left];     } }; 

• c = r - right + 1: 计算右区间 [right, r] 的元素个数。这个区间包含了所有比基准元素大的元素。
• b = right - 1 - (left + 1) + 1: 计算中间区间 [left + 1, right - 1] 的元素个数。这个区间包含了所有等于基准元素的元素。

c >= k:

• 说明第 k 个最大的元素位于右区间，因为右区间中有足够多的元素。如果右区间的大小大于或等于 k，说明第 k 个最大的元素在右区间，所以我们需要递归查找右区间。递归调用 qsort(nums, right, r, k) 来继续寻找。
  b + c >= k:
• 说明第 k 个最大的元素位于中间区间。中间区间包含了所有与基准元素相等的元素。如果 b + c 大于或等于 k，那么第 k 个元素就是基准元素本身，因为它落在中间区间的某个位置。因此，直接返回 key（基准元素）。
  else:
• 说明第 k 个最大的元素不在右区间，也不在中间区间，肯定位于左区间。此时，我们递归查找左区间，递归范围是 [l, left]，并且 k 被调整为 k - b - c，因为我们已经跳过了右区间和中间区间中的元素。

通过这些条件判断，算法有效地缩小了搜索范围，确保每次递归都能迅速逼近目标位置，直到找到第 k 个最大的元素。

47.最小的k个数

题目链接 这个题的话可以不按照从小到大的顺序返回
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

• 示例1：
  • 输入：arr = [3,2,1], k = 2
  • 输出：[1,2] 或者 [2,1]
• 示例2：
  • 输入：arr = [0,1,2,1], k = 1
  • 输出：[0]

解法一：排序（调用容器） NlogN

解法二：利用堆 NlogK

解法三：快速选择算法O(N)

随机选择基准元素+数组分成三块

class Solution { public: vector<int> getLeastNumbers_Solution(vector<int> nums, int k) { srand(time(NULL)); qsort(nums,0,nums.size()-1,k);//没有对整个数组进行排序，而是将前k个数丢到前面去 return {nums.begin(),nums.begin()+k};//返回前k个数 } void qsort(vector<int>&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]<k)swap(nums[++left],nums[i]); else if(nums[i]==k) i++; else swap(nums[--right],nums[i]); } //[l,left][left+1,right-1][right,r] //3.分情况讨论 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(vector<int>&nums,int l,int r) { return nums[rand()%(r-l+1)+l]; } }; 

假设数组已经被分为三部分：

• [l, left]：小于基准值的部分
• [left+1, right-1]：等于基准值的部分
• [right, r]：大于基准值的部分
  这里有三个主要的变量：
• a = left - l + 1：表示小于基准值的元素数量。
• b = right - left + 1：表示等于基准值的元素数量
  a > k：
• 说明前 k 个最小的元素都在小于基准值的部分 [l, left] 中，所以下一步只需要在左侧部分继续递归。
• 调用 qsort(nums, l, left, k)，只递归左侧部分，寻找最小的 k 个元素。
  a + b > k：
• a + b 是小于或等于基准值的元素总数。
• 如果 a + b >= k，说明前 k 个最小的数已经在左侧部分或等于基准值的部分中找到了。
• 在这种情况下，递归结束，不需要继续处理右侧部分，因为前 k 个数已经被找到了。
  else（即 a + b < k）：
• 说明前 k 个最小的数不在小于基准值的部分，也不完全在等于基准值的部分。
• 因此，接下来应该递归处理右侧部分 [right, r]，并且需要继续寻找剩余的 k - a - b 个最小数（因为左侧和中间部分已经有了 a + b 个最小数）。