【优选算法】（第二十三篇）
目录
快速选择算法（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定整数数组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<=10^5
-10^4<=nums[i]<=10^4
讲解算法原理
解法（快速选择算法）：
算法思路：
在快排中，当我们把数组「分成三块」之后： [l, left] [left + 1, right - 1] [right, r] ，我们可以通过计算每⼀个区间内元素的「个数」，进⽽推断出我们要找的元素是在「哪⼀个区间」⾥⾯。
那么我们可以直接去「相应的区间」去寻找最终结果就好了。
编写代码
c++算法代码：
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
srand(time(NULL));
return qsort(nums, 0, nums.size() - 1, k);
}
int qsort(vector<int>& nums, int l, int r, int k)
{
if(l == r) return nums[l];
// 1. 随机选择基准元素
int key = getRandom(nums, l, r);
// 2. 根据基准元素将数组分三块
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) i++;
else swap(nums[--right], nums[i]);
}
// 3. 分情况讨论
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 getRandom(vector<int>& nums, int left, int right)
{
return nums[rand() % (right - left + 1) + left];
}
};java算法代码：
class Solution
{
public int findKthLargest(int[] nums, int k)
{
return qsort(nums, 0, nums.length - 1, k);
}
public int qsort(int[] nums, int l, int r, int k)
{
if(l == r)
{
return nums[l];
}
// 1. 按照随机选择的基准元素，将数组分三块
int key = nums[new Random().nextInt(r - l + 1) + l];
int left = l - 1, right = r + 1, i = l;
while(i < right)
{
if(nums[i] < key) swap(nums, ++left, i++);
else if(nums[i] == key) i++;
else swap(nums, --right, i);
}
// 2. 分情况讨论
int c = r - right + 1, b = right - left - 1;
if(c >= k) return qsort(nums, right, r, k);
else if(c + b >= k) return key;
else return qsort(nums, l, left, k - b - c);
}
public void swap(int[] nums, int i, int j)
{
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}最⼩的k个数（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
输⼊整数数组arr，找出其中最⼩的k个数。例如，输⼊4、5、1、6、2、7、3、8这8个数字，则最⼩的4个数字是1、2、3、4。
⽰例1：
输⼊：arr=[3,2,1],k=2
输出：[1,2]或者[2,1]
⽰例2：
输⼊：arr=[0,1,2,1],k=1
输出：[0]
限制：
0<=k<=arr.length<=10000
0<=arr[i]<=10000
讲解算法原理
解法（快速选择算法）：
算法思路：
在快排中，当我们把数组「分成三块」之后： [l, left] [left + 1, right - 1] [right, r] ，我们可以通过计算每⼀个区间内元素的「个数」，进⽽推断出最⼩的k个数在哪些区间⾥⾯。
那么我们可以直接去「相应的区间」继续划分数组即可。
编写代码
c++算法代码：
class Solution
{
public:
vector<int> getLeastNumbers(vector<int>& nums, int k)
{
srand(time(NULL));
qsort(nums, 0, nums.size() - 1, k);
return {nums.begin(), nums.begin() + k};
}
void qsort(vector<int>& nums, int l, int r, int k)
{
if(l >= r) return;
// 1. 随机选择⼀个基准元素 + 数组分三块
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) i++;
else swap(nums[--right], nums[i]);
}
// [l, left][left + 1, right - 1] [right, r]
// 2. 分情况讨论
int a = left - l + 1, b = right - left - 1;
if(a > k) qsort(nums, l, left, k);
else if(a + b >= k) return;
else qsort(nums, right, r, k - a - b);
}
int getRandom(vector<int>& nums, int l, int r)
{
return nums[rand() % (r - l + 1) + l];
}
};java算法代码：
class Solution
{
public int[] getLeastNumbers(int[] nums, int k)
{
qsort(nums, 0, nums.length - 1, k);
int[] ret = new int[k];
for(int i = 0; i < k; i++)
ret[i] = nums[i];
return ret;
}
public void qsort(int[] nums, int l, int r, int k)
{
if(l >= r) return;
// 1. 随机选择⼀个基准元素 + 数组分三块
int key = nums[new Random().nextInt(r - l + 1) + l];
int left = l - 1, right = r + 1, i = l;
while(i < right)
{
if(nums[i] < key) swap(nums, ++left, i++);
else if(nums[i] == key) i++;
else swap(nums, --right, i);
}
// 2. 分类讨论
int a = left - l + 1, b = right - left - 1;
if(a > k) qsort(nums, l, left, k);
else if(a + b >= k) return;
else qsort(nums, right, r, k - a - b);
}
public void swap(int[] nums, int i, int j)
{
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}原文地址：https://blog.csdn.net/weixin_73861555/article/details/142725395
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！