【刷题篇】分治-快速排序

文章目录

• 1、颜色分类
• 2、 排序数组
• 3、数组中的第K个最大元素
• 4、库存管理 III

1、颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int left=-1;
        int right=n;
        for(int i=0;i<right;)
        {
            if(nums[i]==0)
                swap(nums[++left],nums[i++]);
            else if(nums[i]==2)
                swap(nums[--right],nums[i]);
            else
                i++;
        }
    }
};

2、 排序数组

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

class Solution {
public:
    int getrandkey(vector<int>& nums,int left,int right)
    {
        int r=nums[rand()%(right-left+1)+left];
        return r;
    }
    void qsort(vector<int>& nums,int l,int r)
    {
        if(l>=r)
            return;
        int key=getrandkey(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)
                swap(nums[--right],nums[i]);
            else
                i++;
        }
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }
};

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

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution {
public:
    int getrandkey(vector<int>& nums,int left,int right)
    {
        return nums[rand()%(right-left+1)+left];
    }
    int qsort(vector<int>& nums,int l,int r,int k)
    {
        if(l==r)
            return nums[l];
        int key=getrandkey(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)
                swap(nums[--right],nums[i]);
            else
                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 findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return qsort(nums,0,nums.size()-1,k);
    }
};

4、库存管理 III

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

class Solution {
public:
    int getrandkey(vector<int>& nums,int left,int right)
    {
        return nums[rand()%(right-left+1)+left];
    }
    void qsort(vector<int>& nums, int l,int r,int cnt)
    {
        if(l>=r) return;
        int key=getrandkey(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) swap(nums[--right],nums[i]);//后面的数据是属于未知的所以不用加加
            else i++;
        }
        int a=left-l+1,b=right-1-left;
        if(a>cnt) qsort(nums,l,left,cnt);
        else if(a+b>=cnt) return ;
        else qsort(nums,right,r,cnt-a-b);
    }
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        qsort(stock,0,stock.size()-1,cnt);
        return {stock.begin(),stock.begin()+cnt};
    }
};