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

文章目录

• 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]);elsei++;}}
};

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]);elsei++;}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]);elsei++;}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;elsereturn 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};}
};