leetcode算法之分治-快排

1.颜色分类

颜色分类

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = -1,right=n,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

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 left = l-1,right = r+1,i=l;
        int key = getRandom(nums,l,r);
        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)
    {
        return nums[rand()%(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

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

数组中的第k个最大元素

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];
        //1.随机选择基准元素
        int left = l-1,right=r+1,i=l;
        int key = nums[rand()%(r-l+1)+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]);
        }
        //2.分情况讨论
        //[l,left][left+1,right-1][right,r]
        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);

    }
};
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

4.最小的k个数

最小的k个数

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

    void qsort(vector<int>& arr,int l,int r,int k)
    {
        if(l>=r) return;
        int left = l-1,right=r+1,i=l;
        int key = getRandom(arr,l,r);
        while(i<right)
        {
            if(arr[i]<key) swap(arr[++left],arr[i++]);
            else if(arr[i] == key) i++;
            else swap(arr[--right],arr[i]);
        }
        //[l,left][left+1,right-1][right,r]
        int a = left-l+1,b = right-left-1;
        if(a>k) qsort(arr,l,left,k);
        else if(a+b>=k) return;
        else qsort(arr,right,r,k-a-b);
    }

    int getRandom(vector<int>& arr,int left,int right)
    {
        return arr[rand()%(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