须知
💬 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力! 👍 点赞、收藏与分享:觉得这篇文章对你有帮助吗?别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力! 🚀 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对C++算法感兴趣的朋友,让我们一起进步!
接上篇: 【优选算法篇】揭秘快速排序:分治算法如何突破性能瓶颈(上篇)-CSDN博客
引言:通过上篇文章带大家简单了解“分治(快速排序)算法”,小试牛刀。接下来将让大家感受一下分治(快速排序)在解题的更多妙处。
分治法是一种将一个大问题分解为多个子问题并解决这些子问题的策略,通常包含三个步骤:
分治法的关键在于能否将问题成功分解,并且保证每个子问题都能被有效解决。
快速选择排序(Quick Select)是一种基于快速排序思想的选择算法,它用于找到数组中的第 k 小元素,而不是对数组进行完全排序。它的核心思想如下:
快速选择排序的经典应用主要集中在以下几个领域:
快速选择排序的核心思想是在分治法框架下进行快速查找第 k 小元素,步骤包括:
#include <iostream>
#include <vector>
#include <algorithm>
// 分区函数
int partition(std::vector<int>& nums, int left, int right) {
int pivot = nums[right]; // 选择最右边的元素作为枢纽
int i = left - 1;
for (int j = left; j < right; ++j) {
if (nums[j] < pivot) {
i++;
std::swap(nums[i], nums[j]);
}
}
std::swap(nums[i + 1], nums[right]);
return i + 1;
}
// 快速选择函数
int quickSelect(std::vector<int>& nums, int left, int right, int k) {
if (left == right) return nums[left]; // 只有一个元素时直接返回
int pivotIndex = partition(nums, left, right);
if (k == pivotIndex) {
return nums[k]; // 如果枢纽位置就是第 k 小元素,返回它
} else if (k < pivotIndex) {
return quickSelect(nums, left, pivotIndex - 1, k); // 在左半部分查找
} else {
return quickSelect(nums, pivotIndex + 1, right, k); // 在右半部分查找
}
}
int main() {
std::vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2; // 查找第 2 小的元素
std::cout << "The " << k << "th smallest element is: " << quickSelect(nums, 0, nums.size() - 1, k - 1) << std::endl;
return 0;
}
题目链接:215. 数组中的第K个最大元素 - 力扣(LeetCode)
题目描述:
2.1 算法思路:
核心算法思想
k
大的元素,而不需要对整个数组排序。通过在每次分区后缩小查找的范围,最终定位到第 k
大的元素。
算法流程
getRandom()
函数随机选择一个基准元素(pivot),这能够避免最坏情况(即每次选择的基准元素是当前子数组的最大或最小元素,导致退化为 O(n²) 的时间复杂度)。
k
大元素的位置决定下一步递归:
k
大元素在右边部分,递归到右边部分。
k
大元素就是基准元素,直接返回基准元素。
k
大元素在左边部分,递归到左边部分。
k
大元素时返回。
class Solution
{
public:
// 主函数,找到数组中的第 k 大元素
int findKthLargest(vector<int>& nums, int k)
{
srand(time(NULL)); // 使用当前时间初始化随机数生成器,确保每次执行时选择不同的基准元素
return qsort(nums, 0, nums.size() - 1, k); // 调用快速选择算法的主函数
}
// 快速选择算法的递归实现,返回第 k 大元素
int qsort(vector<int>& nums, int l, int r, int k)
{
if (l == r) return nums[l]; // 如果当前子数组只剩下一个元素,直接返回该元素
int i = l, left = l - 1, right = r + 1; // 初始化三个指针:i、left 和 right
int key = getRandom(nums, l, r); // 随机选择一个基准元素
// 三路分区:小于基准、等于基准和大于基准
while (i < right)
{
if (nums[i] < key)
swap(nums[++left], nums[i++]); // 如果 nums[i] 小于基准,移动到左侧
else if (nums[i] == key)
i++; // 如果 nums[i] 等于基准,跳过当前元素
else
swap(nums[i], nums[--right]); // 如果 nums[i] 大于基准,移动到右侧
}
// 计算基准元素在数组中所占的大小
int b = right - left - 1; // 等于基准元素的数量
int c = r - right + 1; // 大于基准元素的数量
// 根据第 k 大元素的位置来决定下一步的递归
if (c >= k)
return qsort(nums, right, r, k); // 如果第 k 大元素在右侧部分,递归右部分
else if (b + c >= k)
return key; // 如果第 k 大元素是基准元素,返回基准元素
else
return qsort(nums, l, left, k - b - c); // 否则,第 k 大元素在左侧部分,递归左部分
}
// 随机选择一个基准元素
int getRandom(vector<int>& nums, int left, int right)
{
int n = rand(); // 生成一个随机数
return nums[n % (right - left + 1) + left]; // 从区间 [left, right] 中随机选择一个元素
}
};
findKthLargest
:
nums
和一个整数 k
,返回数组中第 k
大的元素。srand(time(NULL))
来初始化随机数种子,确保每次运行时随机数不同。qsort
函数来执行快速选择算法,查找第 k
大元素。qsort
(快速选择算法):
nums
(数组),l
(子数组的左边界),r
(子数组的右边界),k
(第 k 大的元素)。if (l == r)
:如果子数组只包含一个元素,直接返回该元素。key
,并使用三路分区法(类似于快速排序)将数组分为三个部分:小于基准、大于基准和等于基准。k
大的元素。left
和 right
分别指向小于基准和大于基准的元素的边界,i
用来遍历数组。nums[i] < key
,将 nums[i]
移到小于基准的部分。nums[i] == key
,保持该元素位置不动,继续扫描。nums[i] > key
,将 nums[i]
移到大于基准的部分。k
大元素的位置: k
大元素在右侧(大于基准的部分),递归右部分。k
大元素正好是基准元素,返回基准元素。k
大元素在左侧(小于基准的部分),递归左部分。getRandom
:
[left, right]
范围内随机选择一个元素作为基准。通过 rand()
生成一个随机数,并利用模运算确保结果在给定区间内。使用堆(通常是最小堆)可以有效地找到数组中的第 K 大元素。通过构建一个大小为 K 的最小堆,堆中的最小元素将始终是第 K 大元素。
算法思路:
代码实现:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap; // 创建一个最小堆
for (int num : nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop(); // 维持堆的大小为 k
}
}
return minHeap.top(); // 堆顶元素即为第 k 大元素
}
};
时间复杂度:
最直接的解法是将数组排序,然后返回排序后数组的第 K 个元素。由于排序的时间复杂度为 O(n log n),这虽然简单,但在效率上不如快速选择和堆。
算法思路:
代码实现:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater<int>());
return nums[k - 1]; // 排序后返回第 K 个元素
}
};
时间复杂度:
快速排序可以修改为只排序部分数组,达到在 O(n log n) 时间内找到第 K 大元素。通过每次递归仅对部分数组进行排序来优化。
算法思路:
代码实现:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
quickSort(nums, 0, nums.size() - 1, k);
return nums[k - 1];
}
void quickSort(vector<int>& nums, int left, int right, int k) {
if (left < right) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k - 1) return;
else if (pivotIndex < k - 1) quickSort(nums, pivotIndex + 1, right, k);
else quickSort(nums, left, pivotIndex - 1, k);
}
}
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; j++) {
if (nums[j] <= pivot) {
swap(nums[i], nums[j]);
i++;
}
}
swap(nums[i], nums[right]);
return i;
}
};
时间复杂度:
如果数组中的元素范围比较小,可以使用计数排序来找出第 K 大元素。计数排序在元素范围已知且较小的情况下非常高效。
算法思路:
代码实现:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int maxNum = *max_element(nums.begin(), nums.end());
vector<int> count(maxNum + 1, 0);
// 统计每个数字的出现频率
for (int num : nums) {
count[num]++;
}
// 从最大值开始查找第 K 大元素
for (int i = maxNum; i >= 0; i--) {
if (count[i] > 0) {
k -= count[i];
if (k <= 0) return i;
}
}
return -1; // 默认情况不应到达
}
};
时间复杂度:
该算法实现了 快速选择(Quick Select)算法来查找数组中的第 k
大元素,使用了随机化和三路分区的策略来提高效率。通过随机选择基准元素,避免了最坏情况的发生,通常在平均情况下,算法的时间复杂度为 O(n),比直接排序(O(n log n))更高效。
题目链接:面试题 17.14. 最小K个数 - 力扣(LeetCode)
题目描述:
3.1 算法思路:
qsort
是一个递归函数,其目标是根据基准值将数组分为两部分,最终将最小的 K 个元素放到数组的前 K 个位置。class Solution
{
public:
vector<int> smallestK(vector<int>& arr, int k)
{
srand(time(NULL)); // 初始化随机数种子
qsort(arr, 0, arr.size()-1, k); // 调用快速选择函数
return {arr.begin(), arr.begin() + k}; // 返回数组中最小的 K 个元素
}
void qsort(vector<int>& arr, int l, int r, int k)
{
if(l >= r) return; // 如果区间内只有一个元素,结束递归
int left = l - 1, right = r + 1, i = l;
int key = getRandom(arr, l, r); // 随机选择一个基准元素
while(i < right)
{
if(arr[i] < key)
swap(arr[++left], arr[i++]); // 将小于基准的元素移到左边
else if(arr[i] == key)
i++; // 如果等于基准元素,直接跳过
else
swap(arr[--right], arr[i]); // 将大于基准的元素移到右边
}
int a = left - l + 1, b = right - left - 1;
if(a > k)
qsort(arr, l, left, k); // 如果前 a 个元素已经包含了 K 个最小的元素,递归左半部分
else if(a + b >= k)
return; // 如果已经找到前 K 个最小的元素,结束
else
qsort(arr, right, r, k - a - b); // 否则递归右半部分
}
int getRandom(vector<int>& arr, int left, int right)
{
return arr[rand() % (right - left + 1) + left]; // 随机选择一个基准元素
}
};
smallestK
函数:
arr
(整数数组),k
(需要找到最小的 K 个元素)。
qsort
进行快速选择,递归地确定前 K 个最小的元素,并且返回前 K 个元素作为结果。
qsort
函数:
getRandom
函数:
rand() % (right - left + 1) + left
是一个经典的随机选择区间元素的方法。
递归分治过程:
a
:表示小于基准的元素数量。
b
:表示等于基准的元素数量。
a >= k
,意味着最小的 K 个元素都在基准左边,因此递归处理左边部分。
a + b >= k
,说明当前基准元素是第 K 小的元素,直接返回,不需要再递归。
a + b < k
,递归处理右边部分,寻找剩余的第 k - a - b
小的元素。
最直观的方法是对数组进行排序,然后返回前 k
个元素。
步骤:
arr
进行升序排序。
k
个元素。
代码实现:
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k) {
sort(arr.begin(), arr.end()); // 对数组进行升序排序
return vector<int>(arr.begin(), arr.begin() + k); // 返回前 k 个元素
}
};
时间复杂度:
O(nlogn)
,其中 n
是数组的长度。
k
个元素的时间复杂度是 O(k)
,但通常可以认为 O(k)
比 O(nlogn)
要小,因此总时间复杂度是 O(nlogn)
。
空间复杂度:
O(n)
的额外空间来存储排序后的数组。
使用最小堆来维护当前数组中最小的 k
个元素。可以通过构建一个大小为 k
的最小堆来解决。
步骤:
k
的最小堆(或者最大堆,下面我们将使用最大堆)。
k
,则直接将当前元素加入堆中。
k
,则与堆顶元素比较,如果当前元素更小,则弹出堆顶元素,并将当前元素加入堆中。
k
个元素。
代码实现:
#include <queue>
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k) {
priority_queue<int> maxHeap; // 最大堆
for (int num : arr) {
if (maxHeap.size() < k) {
maxHeap.push(num); // 堆的大小小于 k,直接加入
} else if (num < maxHeap.top()) {
maxHeap.pop(); // 弹出堆顶元素
maxHeap.push(num); // 加入当前元素
}
}
vector<int> result;
while (!maxHeap.empty()) {
result.push_back(maxHeap.top());
maxHeap.pop();
}
reverse(result.begin(), result.end()); // 由于是最大堆,最后要反转结果
return result;
}
};
时间复杂度:
O(log k)
时间。
O(n)
次操作。
O(n log k)
。
空间复杂度:
k
的堆,空间复杂度为 O(k)
。
k
个元素这是一种通过逐步维护前 k
个元素的方法。可以使用 std::partial_sort
来高效地获取数组的前 k
个最小元素。
步骤:
std::partial_sort
对数组进行排序,只将前 k
个元素排序,而不对整个数组进行排序。
k
个元素。
代码实现:
#include <algorithm>
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k) {
partial_sort(arr.begin(), arr.begin() + k, arr.end());
return vector<int>(arr.begin(), arr.begin() + k);
}
};
时间复杂度:
std::partial_sort
的时间复杂度是 O(n log k)
。空间复杂度:
O(n)
,主要是由于排序时可能需要额外的空间。优点:
k
比较小或者数组很大的时候。
缺点:
这段代码通过 快速选择算法 来有效地找到数组中最小的 K 个元素。算法利用随机化技术避免了最坏情况,并通过分治策略将时间复杂度保持在 O(n)(平均情况下),非常适合大规模数据的处理。
我们发现,排序法适用于简单场景,最小堆适合 K 较小的数据集,快速选择算法在大数据量下效率最高,部分排序法则能够快速得到前 K 个元素,尤其适用于空间敏感和实时计算的场景。
在处理数组元素的选择问题时,选择合适的算法不仅能提高效率,也能在大数据和高性能计算需求中展现出明显优势,特别是在 时间复杂度敏感 和 数据量较大的 应用中。
通过上面几个例题:「最小的 K 个数字」的多种解法、「快速选择算法」的应用、最小堆排序、以及排序法,我们总结出高效解决数组中最小 K 个元素问题的几种常见策略。 排序法、最小堆、快速选择算法和部分排序法在数组问题中有着广泛的应用。它们的本质是在数组中寻找前 K 个元素,虽然方法不同,但都具有显著的时间复杂度优化特性。
partial_sort
来进行部分排序,只排序前 K 个元素,时间复杂度为 O(n log k),它能够在不完全排序的情况下快速获得结果,适合对部分元素有要求的场景。
路虽远,行则将至;事虽难,做则必成
亲爱的读者们,下一篇文章再会!!!
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有