【算法】分治-快排

个人主页 ： zxctscl
如有转载请先通知

前言

分治就是分而治之

1. 75. 颜色分类

1.1 分析

就是把数组中的元素分为三块，0全部在左边，1全部在中间，2全部在右边。
这里要用到三个指针，一个i指针用来遍历，一个left用来存放0区域的最后侧，一个用来存放2区域的最左侧。
那么区间就分成了4个

只需要判断nums[i]的值是什么，然后把它放在对应区域。把数组遍历一遍就行，最终i只要等于right就结束遍历，此时中间已经没有要确定区域的数了。

1.2 代码

class Solution {
public:
    void sortColors(vector<int>& 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]);
           }
        }
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. 912. 排序数组

2.1 分析

可以先选择一个元素作为基准，把比它小的元素都放在它的左边，把它大的都放在右边，中间放的数就和它相等，这样数组就分为三个区间，递归找一下左边，再递归找一下右边，直到数组全部被排好。

为了减少时间复杂度，选取基准值的时候选取随机数。

2.2 代码

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 k=getRandom(nums,l,r);
        int i=l,left=l-1,right=r+1;
         while(i<right)
        {      
            if(nums[i]<k)
            {
                swap(nums[++left],nums[i++]);
            }
           else if(nums[i]==k)i++;
           else{
            swap(nums[--right],nums[i]);
           }
        }
        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];
     }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

3.1 分析

和上面那题一样，这里也将区间分三块。
随机选取一个基准元素k，根据这个基准元素将区间分三部分，左边都是小于k的，中间都是等于k的，有边都是大于k的。
题目要求找到的是第k大元素，那么在三个区域都有可以，但是如果确定这个第k大元素是在某一个区域的时候，那么剩下的两个区域就都不用考虑。
左边元素个数为a,中间为b，右边为c。
第一种如果在c区域，那么c大于等于k的，因为c区域放的是是大值区域，如果存在第k大的，那么最有可能就在c中，只需要c大于等于k就一定在。
在第二种情况找的时候，就说明第一种情况不存在，在中间的区域，那么就直接返回k就行，因为中间元素都是相等的。
第三种情况，前面两种情况都不存在，那么就在左边区间找，右边区域和中间区域都没有，那么找的就是第k-b-c大的元素。

3.2 代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
         srand(time(NULL));
         return qsort(nums, 0, nums.size() - 1,k);
    }

   int qsort(vector<int>& nums, int l, int r,int k)
   {
      if(l==r)return nums[l];
      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]);
           }
        }
        //分情况讨论
        int c=r-right+1,b=right-left-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)
     {
        int r=rand();
        return nums[r%(right-left+1)+left];
     }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

4. LCR 159. 库存管理 III

4.1 分析

解法一：
可以直接排序，把前面的cnt个数重新放在一个vector表里面返回就行。

解法二：用快速选择算法
就是前面所提到的随机选择基准元素k，把数组分三个区间。

然后统计每一个区间的个数，此时就分为三种情况：
第一种情况：第k小，如果a>k就先从第一个区间找。
第二种情况：a+b大于等于k，那么就直接返回k就行，这个区间值都是相等的。
第三种情况：前面两种情况都不成立，说明这个k在右边这个区域，找k-a-b个元素就可以。

4.2 代码

解法一：

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
    sort(stock.begin(),stock.end());
    vector<int> v;
    for(int i=0;i<cnt;i++)
    {
        v.push_back(stock[i]);
    }
    return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

解法二：

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
         srand(time(NULL));
         qsort(stock, 0, stock.size() - 1,cnt);
         return {stock.begin(),stock.begin()+cnt};
    }

   void qsort(vector<int>& stock, int l, int r,int k)
   {
       if(l>=r)return;
       int key=getRandom(stock,l,r);
       int i=l,left=l-1,right=r+1;

         while(i<right)
        {      
          if(stock[i]<key) swap(stock[++left],stock[i++]);
           else if(stock[i]==key)i++;
           else swap(stock[--right],stock[i]);
        }

        //分情况讨论
        int a=left-l+1,b=right-left-1;
        if(a>k)qsort(stock,l,left,k);
        else if(a+b>=k) return;
        else  qsort(stock,right,r,k-a-b); 
         }

      int getRandom(vector<int>&stock,int left,int right)
     {
        int r=rand();
        return stock[r%(right-left+1)+left];
     }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

有问题请指出，大家一起进步！！！