分治—快速选择算法
文章目录
- 🍇215.数组中的第K个最大元素
- 🍈1. 题目
- 🍉2. 算法原理
- 🍊3. 代码实现
- 🍋LCR 159. 库存管理 III
- 🍌1. 题目
- 🍍2. 算法原理
- 🥭代码实现
🍇215.数组中的第K个最大元素
🍈1. 题目
题目链接:215. 数组中的第K个最大元素 - 力扣(LeetCode)
给定整数数组 nums
和整数 k
,请返回数组中第 **k**
个最大的元素。
请注意,你需要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。
你必须设计并实现时间复杂度为 O(n)
的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示:
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
🍉2. 算法原理
解法一:优先级队列(堆)
一般看到第k
个什么什么元素,基本都是采用堆来解决,STL
里面内置了堆,也就是priority_queue
优先级队列,如果是竞赛或者是考试,可以直接用,如果是平时训练,可以自己手搓一个出来。
解法二:快速选择算法(快排)
快速选择算法是基于快排的
快排的核心思路:从数组里面随机选择一个基准元素,将数组分为三部分,即:
>key
、==key
、<key
将数组分为三个区域之后,我们只需要看这个第k大的元素落在哪个区间即可,那如何确定第k
大的元素在哪个区域,也是三种情况:
-
设左边区间的元素个数为
a
个,中间区域的元素为b
个,右边区间的元素个数为c
个c >= k
,又区间都是大元素,我们看看有几个大元素,就能知道,第k
个是不是在这个区间内,即[right,l]
- 当第一个条件不成立时,我们去中间区域找,也就是
b+c >= k
,在这个区域直接返回即可 - 上述两个条件都不成立的情况下,那我们只能去左侧区域
[l,left]
寻找,这时候要找的就是第k-b-c
大的元素了
🍊3. 代码实现
堆:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
int n = nums.size();
buildMaxHeap(nums, n);
for(int i=0;i<k-1;i++)
{
swap(nums[0],nums[n-1-i]);
Adjustdown(nums,n-1-i,0);
}
return nums[0];
}
void buildMaxHeap(vector<int>& nums , int sz)
{
for(int i = (sz - 1 -1)/2; i>=0; i--)
{
Adjustdown(nums,sz,i);
}
}
void Adjustdown(vector<int>& nums, int sz, int parent)
{
int child = parent*2+1; //默认左孩子大
while(child<sz)
{
if(child+1 < sz && nums[child] < nums[child+1])
{
child++;
}
if(nums[child] >nums[parent])
{
swap(nums[child],nums[parent]);
parent = child;
child = parent*2+1;
}
else break;
}
}
};
快速选择:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
srand(time(NULL));
return quickSort(nums,0,nums.size()-1,k);
}
int quickSort(vector<int>& nums, int l, int r, int k)
{
if(l == r) return nums[l];
int key = getRandom(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++;
}
//查看k在哪个区间
int c = r - right + 1,
b = right - left -1;
if(c >= k) return quickSort(nums,right,r,k);
else if(b+c >= k) return key;
else return quickSort(nums,l,left,k-b-c);
}
int getRandom(vector<int>& nums, int l, int r)
{
return nums[rand()%(r - l + 1) + l];
}
};
运行结果:
🍋LCR 159. 库存管理 III
🍌1. 题目
题目链接:LCR 159. 库存管理 III
仓库管理员以数组 stock
形式记录商品库存表,其中 stock[i]
表示对应商品库存余量。请返回库存余量最少的 cnt
个商品余量,返回 顺序不限。
示例 1:
输入:stock = [2,5,7,4], cnt = 1
输出:[2]
示例 2:
输入:stock = [0,2,3,6], cnt = 2
输出:[0,2] 或 [2,0]
提示:
0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000
🍍2. 算法原理
这题就和上面这题差不多,这个是求最小的几个元素,顺序不限,解法很多
解法一:排序
直接排升序,然后返回前k
个元素即可,时间复杂度O(N*logN)
解法二:堆
建一个大小为k
的大根堆,将数据丢进这个堆,最后堆里面的元素就是我们要找的元素,时间复杂度O(N*logK)
详情可以看此篇文章数据结构——二叉树的
3.3Top-K
内容
解法三:快速选择算法
依旧是快排的核心思想:选取基准元素+数组分三块,时间复杂度为O(N)
还是这张图:
🥭代码实现
class Solution {
public:
vector<int> inventoryManagement(vector<int>& stock, int cnt)
{
srand(time(NULL));
quickSort(stock, 0, stock.size()-1, cnt);
return {stock.begin(),stock.begin()+cnt};
}
void quickSort(vector<int>& nums ,int l, int r, int k)
{
if(l >= r) return;
int key = getRandom(nums,l,r);
int left = l-1,
right = r+1,
i = l;
while(i<right)
{
if(nums[i] < key) swap(nums[++left],nums[i++]);
else if(nums[i] > key) swap(nums[--right],nums[i]);
else i++;
}
//[l,left] [left+1,right-1] [right,r]
int a = left - l + 1,
b = right - left - 1;
if(a > k) quickSort(nums,l,left,k);
else if(a+b >= k) return;
else quickSort(nums,right,r,k-a-b);
}
int getRandom(vector<int>& nums, int l, int r)
{
return nums[rand() % (r-l+1) + l];
}
};
运行结果:
运行结果: