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

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=0的话，那么我们将当前位置的0和nums[left+1]位置的数进行互换操纵，
但是假如我们此时i的位置就是left+1的话，那么我们将left和left+1的位置进行互换操纵，但是我们互换后我们的left还是要今后面移动，不如我们先让left先进行++操纵
我们更换下代码的思路，假如我们当前的nums=0的话，我们直接将nums[++left]和nums[i++]进行互换，我们先将left++和i的位置互换，互换完成之后我们的i再今后面进行移动的操纵
假如我们的nums=1的话，那么我们直接将i++就行了，由于我们此时的[left+1,i-1]范围内都是1
假如我们此时的nums=2的话，我们将此时的位置和right-1进行互换操纵
代码的话我们可以先让right–，然后再将我们和我们i位置的互换，如许我们的指针也进行了移动的操纵，此时我们将原先right-1的位置和i位置的元素进行互换了，那么我们此时的i位置的元素还是带扫描的元素，由于我们将后面的元素挪动到前面来了，我们此时是不须要动i的
思路如下

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

1. class Solution
3. {
5. public:
7.     void sortColors(vector<int>& nums)
9.     {
11.         int n =nums.size();
13.         //三个指针
15.         int left=-1,right=n,i=0;
17.         while(i<right)//当我们的i和right相遇之后的话循环就结束了
19.         {
21.             if(nums[i]==0)swap(nums[++left],nums[i++]);
23.             else if(nums[i]==1) i++;
25.             else swap(nums[--right],nums[i]);
27.         }
29.   
31.     }
33. };

复制代码

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<key的话，那么我们须要将nums[++left]位置和num[i+1]的位置进行互换
假如即是k的话，那么就是i++
假如大于k的话，那么就是互换nums[–right]和nums进行互换的，这里互换完成之后我们是 不须要进行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]

1. class Solution
3. {
5. public:
7.     vector<int> sortArray(vector<int>& nums)
9.     {
11.   
13.         srand(time(NULL));//种下一个随机数种子
15.         qsort(nums,0,nums.size()-1);//将数组、左指针和右指针的下标传过去
17.         return nums;
19.     }
21.   
23.     //快排
25.     void qsort(vector<int>&nums,int l,int r)
27.     {
29.         if(l>=r) return ;//要么你的区间是只有一个元素，要么就是区间不存在的
31.   
33.         //数组分三块
35.         int key=getRandom(nums,l,r);//getRandom可以根据数组和左区间右区间进行随机数的获取操作
37.   
39.         //进行三个指针的初始化操作
41.         int i=l,left=l-1,right=r+1;//left从区间的最左侧开始，right从区间的最右侧开始
43.         while(i<right)
45.         {
47.             if(nums[i]<key)
49.             {
51.                 swap(nums[++left],nums[i++]);
53.             }
55.             else if(nums[i]==key)
57.             {
59.                 i++;
61.             }
63.             else
65.             {
67.                 swap(nums[--right], nums[i]);
69.             }
71.   
73.         }
75.   
77.         //分成三块之后
79.         //[l,left] [left+1,right-1]  [right,r]
81.         qsort(nums,l,left);
83.         qsort(nums,right,r);
85.         //通过递归，我们能够将每个子数组进一步分割，直到它们只有一个元素为止，这时数组已经是有序的。
87.     }
89.     int getRandom(vector<int>&nums,int left,int right)
91.     {
93.         int r=rand();
95.         return nums[r%(right-left+1)+left];
97.     }
99. };

复制代码

选择一个基准元素（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
我们之前使用优先级队列进行标题办理

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

复制代码

这里我们将元素放到优先级队列中，默认是大堆，我们从数组的位置开始放，然后第k个最大的数字就在我们的堆顶了，然后我们循环进行删除堆顶数据，循环k-1次，末了得到的就是我们的堆顶的数据
但是这里的话我们使用分治的方法，基于快排而实现的选择算法
数组分三块+随机选择基准元素
假如我们的第k大落在了>key的区间上，那么我们左边的区间就不消去找了

1. class Solution {
3. public:
5.     int findKthLargest(vector<int>& nums, int k)
7.     {
9.         srand(time(NULL));//种一个随机数的种子
11.         return qsort(nums,0,nums.size()-1,k);//直接利用qsort返回最终的结果就行了
13.     }
15.     int qsort(vector<int>&nums,int l,int r,int k)
17.     {
19.         if(l==r) return nums[l];//如果区间只有一个元素的话，那么我们直接返回nums[l]
21.   
23.         //1.随机选择一个基准元素
25.         int key=getRandom(nums,l,r);
27.   
29.         //2.根据基准元素将数组分成三块
31.         int left=l-1,right=r+1,i=l;
33.         while(i<right)
35.         {
37.             if(nums[i]<key)swap(nums[++left],nums[i++]);
39.             else if(nums[i]==key)i++;
41.             else swap(nums[--right],nums[i]);
43.         }
45.   
47.         //3.分情况讨论，去哪个区间去寻找
49.         int c=r-right+1;//[right,r]这个区间的元素的个数
51.         int b=right-1-(left+1)+1;//[left+1,right-1]
53.         if(c>=k) return qsort(nums,right,r,k);//落在右边的区域上
55.         else if(b+c>=k)return key;//落在中间的这个区域上
57.         else return qsort(nums,l,left,k-b-c);
59.     }
61.   
63.     int getRandom(vector<int>&nums,int left,int right)
65.     {
67.         return nums[rand()%(right-left)+left];
69.     }
71. };

复制代码

• 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)
随机选择基准元素+数组分成三块

1. class Solution {
2. public:
3.     vector<int> getLeastNumbers_Solution(vector<int> nums, int k)
4.     {
5.         srand(time(NULL));
6.         
7.         
8.         qsort(nums,0,nums.size()-1,k);//没有对整个数组进行排序，而是将前k个数丢到前面去
9.         
10.         return {nums.begin(),nums.begin()+k};//返回前k个数
11.         
12.     }
13.     void qsort(vector<int>&nums,int l,int r,int k)
14.     {
15.         if(l>=r) return ;//先处理特殊的情况
16.         
17.         //1.随机选择一个基准元素+数组分三块
18.         int key=getRandom(nums,l,r);
19.         
20.         //2.数组分三块
21.         int left=l-1,right=r+1,i=l;
22.         while(i<right)
23.         {
24.             if(nums[i]<k)swap(nums[++left],nums[i]);
25.             else if(nums[i]==k) i++;
26.             else swap(nums[--right],nums[i]);
27.         }
28.         
29.         //[l,left][left+1,right-1][right,r]
30.         
31.         //3.分情况讨论
32.         int a=left-l+1;
33.         int b =right-left+1;
34.         if(a>k) qsort(nums,l,left,k);
35.         else if(a+b>k)return ;
36.         else qsort(nums,right,r,k-a-b);
37.     }
38.     int getRandom(vector<int>&nums,int l,int r)
39.     {
40.         return nums[rand()%(r-l+1)+l];
41.     }
42.    
43. };

复制代码

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

• [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 个最小数）。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。