【LeetCode热题100】分治-快排

本篇博客记录分治快排的4道题目：颜色分类、排序数组、数组中的第K个最大元素、数组中最小的N个元素（库存管理）。

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

题目分析：本题的目的旨在将nums的元素0、1、2分成三块，打算采取三指针的方法。使用left、right、i三个变量，其中，left指向全0区间的最右侧，right指向全2区间的最左侧，i指向待扫描的下一个元素，这样就把整个区间划分为4块，包括：

[0,left]：全0区域

[left+1,i-1]：全1区域

[i,right-1]：待扫描的区域

[right,n-1]：全2区域

划分好区域后，刚开始让left指向nums的左侧，即left=-1，right指向nums的右侧，即right=n，i指向nums中的第一个元素，nums[i]就会有三种情况：0、1、2。对于这三种情况，处理的动作如下图：

class Solution {
public:int GetRef(vector<int>& nums , int left , int right){return nums[rand()%(right - left + 1) + left];}void _sortArray(vector<int>& nums, int left, int right){if(left >= right) return;int ref = GetRef(nums, left, right);int l = left - 1, r = right + 1, i = left;while(i < r){if(nums[i] < ref) swap(nums[++l],nums[i++]);else if(nums[i] == ref) i++;else swap(nums[--r],nums[i]);}//[left,l] [l+1,r-1] [r,right] _sortArray(nums,left,l);_sortArray(nums,r,right);}vector<int> sortArray(vector<int>& nums) {srand(time(NULL));_sortArray(nums, 0 , nums.size() - 1);return nums;}
};

题目分析：我们实现快排要用到“颜色分类”这道题的思想，向数组划分为三块，

这样迭代一次之后，[left+1,right-1]之间的元素已经排好，继续递归[0,left]和[right,n-1]即可。

在选择基准元素key时，我们可以使用随机的方式选取，ref = nums[rand()%(right-left+1)+left]。

class Solution {
public:int GetRef(vector<int>& nums,int left, int right){return nums[rand()%(right-left+1)+left];}int sort(vector<int>& nums,int left, int right, int k){if(left == right) return nums[left];//1.随机选择基准元素int ref = GetRef(nums, left, right);//2.根据基准元素将数组分三块int l = left-1,r = right+1;for(int i = left ; i < r ; ){if(nums[i] < ref) swap(nums[i++],nums[++l]);else if(nums[i] > ref) swap(nums[i],nums[--r]);else i++;}//3.分情况讨论//[left,l][l+1,r-1][r,right]int c = right - r + 1, b = r - l -1;if(c >= k) return sort(nums,r,right,k);else if(b+c >= k) return ref;else return sort(nums,left,l,k-b-c);}int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return sort(nums,0,nums.size()-1,k);}
};

题目分析：这道题的基础依然是上面数组分三块+随机选择基准元素的思想，我们第一次将数组分成三块，[left,l][l+1,r-1][r,right]，假设这三个区间的长度分别是a、b、c，然后分情况讨论：

1）c>=k，去[r,right]，找第k大

2）b+c>=k，返回ref

3）如果1）和2）不成立，去[l,left]，找第k-b-c大        

class Solution {
public:vector<int> inventoryManagement(vector<int>& nums, int cnt) {srand(time(nullptr));qsort(nums,0,nums.size()-1,cnt);return {nums.begin(),nums.begin()+cnt};}int GetRef(vector<int>& nums,int left,int right){return nums[rand()%(right-left+1)+left];}void qsort(vector<int>& nums,int left,int right,int cnt){if(left == right) return;int ref = GetRef(nums,left,right);int l = left - 1,r = right + 1,i = left;while(i < r){if(nums[i] < ref) swap(nums[++l],nums[i++]);else if(nums[i] > ref) swap(nums[--r],nums[i]);else i++;}//[left,l][l+1,r-1][r,right]int a = l - left + 1,b = r - 1 - (l + 1) + 1,c = right -r + 1;if(a > cnt) qsort(nums,left,l,cnt);else if(a + b >= cnt) return;else qsort(nums,r,right,cnt - a - b);}
};

题目分析：这道题我们有多种解法，解法1是把这些数放到一个容器中，然后进行排序，时间复杂度是OlogN。解法2是把这些数放到一个大堆里，取堆顶元素，时间复杂度是OlogK。我们这里用第三种解法，快速排序，也是利用数组分三块+随机选择基准元素的思想，在使用这个排序完一遍后，数组被分成了三块，[left,l][l+1,r-1][r,right]，假设这几块的区间长度分别为a、b、c：

① a>k，继续在[left,l]中找出最小的元素。

② a+b>=k，直接返回

③ ①和②都不成立，找[right,r]中最小的k-a-b个元素，在加上[left,l]和[l+1,r-1]之间的元素。