深度解析之算法之分治（快排）
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个最小数）。
