【优选算法---分治】快速排序三路划分(颜色分类、快速排序、数组第K大的元素、数组中最小的K个元素)
一、颜色分类
题目链接:
75. 颜色分类 - 力扣(LeetCode)
题目介绍:
给定一个包含红色、白色和蓝色、共 n
个元素的数组 nums
,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0
、 1
和 2
分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
n == nums.length
1 <= n <= 300
nums[i]
为0
、1
或2
思路:
这个题目的要求其实就是将0放到最左边,将1放到中间将2放到最后边,思路就是将数组划分为三个部分
- [0, left)内的元素都是 0
- [left , cur - 1] 内的元素都是 1 ;
- [cur, right] 内的元素是待定元素;
- (right, n] 内的元素都是 2 。
当cur遍历到0,交换nums[cur]和nums[left],由于交换前left所指元素一定是1,所以cur和left都可以++。
当cur遍历到1,cur++;
当cur遍历到2,交换nums[cur]和nums[right],right可以--,但是由于交换前right所指元素依旧是待定元素,所以cur不能++,还要判断一下
class Solution {
public:
void sortColors(vector<int>& nums) {
int left = 0;
int right = nums.size()-1;
int cur=left;
while (cur <= right) {
if (nums[cur] ==0) {
swap(nums[left], nums[cur]);
left++;
cur++;
} else if (nums[cur] == 1) {
cur++;
} else {
swap(nums[cur], nums[right]);
right--;
}
}
}
};
二、快速排序
题目链接:
912. 排序数组 - 力扣(LeetCode)
题目介绍:
给你一个整数数组 nums
,请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O(nlog(n))
,并且空间复杂度尽可能小。
1 <= nums.length <= 5 * 10^4
-5 * 104 <= nums[i] <= 5 * 10^4
思路:
与上面的题思路相同,不过我们需要先选择一个基准元素,让这个基准元素左边都是小于他的值,右边都是大于他的值,这样这个基准元素在数组中就排序好了。接下来就是排序左边的区间和右边的区间。
注意,数组中选择的那个基准元素可能存在很多个,一轮排序后 [left,right] 区间都是key,所以这段区间都不需要排序了,只需要排【begin,left-1】和【right+1,end】区间。
假设一个数组全是一样的值,这样三路划分的效率就很块,因为cur就会不断向后遍历,直到碰到right(end),其效率就是O(N)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
qsort(nums,0,nums.size()-1);
return nums;
}
void qsort(vector<int>& nums, int begin, int end) {
// 进了这个区间一定能找到
if (begin >= end)
return;
int key = nums[begin];
int left = begin;
int right = end;
int cur = left + 1;
// 分成三块
while (cur <= right) {
if (nums[cur] < key) {
swap(nums[left++], nums[cur++]);
} else if (nums[cur] == key) {
cur++;
} else {
swap(nums[right--], nums[cur]);
}
}
qsort(nums, begin, left - 1);
qsort(nums, right + 1, end);
}
};
三、数组的第K个最大元素
题目链接:
215. 数组中的第K个最大元素 - 力扣(LeetCode)
题目介绍:
给定整数数组 nums
和整数 k
,请返回数组中第 k
个最大的元素。
请注意,你需要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。
你必须设计并实现时间复杂度为 O(n)
的算法解决此问题。
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 10
思路:
首先我们可以选择一个基准元素,采用三路划分排序一遍,此时 key的位置就排序好了,虽然此时他的左右两边都是无序的,但是此时我们可以判断一下,如果右边的元素个数大于等于k,那说明第k大的元素就在右边,那我们就不用管左边了,如果中间的元素加上右边的元素才大于等于k,那说明第k大的元素就是key,否则我们就到左边找第( k-右边元素数量-中间元素数量)大的元素,这样的算法是非常快的,因为我们不需要将数组完全的排好序。
其次,只要进入到了某个区间找元素,那就说明这值一定在这个区间中,所以当begin>=end时我们就可以返回nums[begin]
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return qsort(nums,0,nums.size()-1,k);
}
int qsort(vector<int>& nums,int begin,int end,int k)
{
//进了这个区间一定能找到
if(begin>=end)return nums[begin];
int key=nums[begin];
int left=begin;
int right=end;
int cur=left+1;
//分成三块
while(cur<=right)
{
if(nums[cur]<key)
{
swap(nums[left++],nums[cur++]);
}
else if(nums[cur]==key)
{
cur++;
}
else
{
swap(nums[right--],nums[cur]);
}
}
int c=end-right;
int b=right-left+1;
if(c>=k)return qsort(nums,right+1,end,k);
else if(b+c>=k)return key;
else return qsort(nums,begin,left-1,k-b-c);
}
};
四、数组中最小的k个数
题目链接:
LCR 159. 库存管理 III - 力扣(LeetCode)
题目介绍:
仓库管理员以数组 stock
形式记录商品库存表,其中 stock[i]
表示对应商品库存余量。请返回库存余量最少的 cnt
个商品余量,返回 顺序不限。
思路:
与上一题的思路一样,我们先选择一个基准元素采用三路划分,将数组分为左中右三部分,如果左边的数量大于等于k,那说明最小的k个数就在左边,就到左边找,中间和右边不管了。如果左边和中间加起来的数量才大于等于k,那就可以直接返回,因为前k个元素已经在左边和中间了,虽然他们不是完全有序的。否则的话,我们就要到右边找最小的(k-a-b)个数了
class Solution {
public:
vector<int> inventoryManagement(vector<int>& nums, int k) {
qsort(nums,0,nums.size()-1,k);
return {nums.begin(),nums.begin()+k};
}
void qsort(vector<int>& nums,int begin,int end,int k)
{
if(begin>=end) return;
int key=nums[begin];
int left=begin,right=end;
int cur=left+1;
//分为三块
while(cur<=right)
{
if(nums[cur]<key)
swap(nums[left++],nums[cur++]);
else if(nums[cur]==key)
cur++;
else
swap(nums[right--],nums[cur]);
}
// 判断
int a=left-begin;
int b=right-left+1;
if(a>=k) qsort(nums,begin,left-1,k);
else if(a+b>=k) return;
else qsort(nums,right+1,end,k-a-b);
}
};