C++ 找出数组中最大的 k 个元素(Find k largest elements in an array)

目录例如【朴素方法】使用排序朴素方法示例代码【预期方法】使用优先级队列最小堆预期方法示例代码【替代方法】使用快速选择算法快速排序参考替代方法示例代码如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个数组arr[]和一个整数k任务是找出给定数组中最大的 k 个元素。输出数组中的元素应按降序排列。例如输入 [1, 23, 12, 9, 30, 2, 50]k 3输出[ 50, 30, 23]输入 [11, 5, 12, 9, 44, 17, 2]k 2输出[ 44, 17]【朴素方法】使用排序其思路是将输入数组按降序排列使数组中的前k 个元素成为最大的k 个元素。朴素方法示例代码// C program to find k largest elements in an// array using sorting#include iostream#include vector#include algorithmusing namespace std;vectorint kLargest(vectorint arr, int k) {// sort the given array in descending ordersort(arr.begin(), arr.end(), greaterint());// store the first k element in result arrayvectorint res(arr.begin(), arr.begin() k);return res;}int main() {vectorintarr {1, 23, 12, 9, 30, 2, 50};int k 3;vectorint res kLargest(arr, k);for(int ele : res)cout ele ;return 0;}输出50 30 23时间复杂度O(n * log n)辅助空间O(1)【预期方法】使用优先级队列最小堆其思路是在遍历数组的过程中每一步都记录下最大的 k 个元素。为此我们使用最小堆。首先将初始的 k 个元素插入最小堆。之后对于每个后续元素我们将其与堆顶元素进行比较。由于最小堆的堆顶元素是这 k 个元素中最小的如果当前元素大于堆顶元素则意味着堆顶元素不再是最大的 k 个元素之一。在这种情况下我们移除堆顶元素并插入更大的元素。完成整个遍历后堆将恰好包含数组中最大的 k 个元素。预期方法示例代码// C program to find the k largest elements in the// array using min heap#include iostream#include vector#include queue#include algorithmusing namespace std;// Function to find the k largest elements in the arrayvectorint kLargest(vectorint arr, int k) {// Min Priority Queue (Min-Heap) with first k// elements of the arraypriority_queueint, vectorint, greaterintminH(arr.begin(), arr.begin() k);// Travers n - k elementsfor (int i k; i arr.size(); i) {// If the top of heap is less than the arr[i]// then remove top element and insert arr[i]if(minH.top() arr[i]) {minH.pop();minH.push(arr[i]);}}vectorint res;// Min heap will contain only k// largest elementwhile (!minH.empty()) {res.push_back(minH.top());minH.pop();}// Reverse the result array, so that all// elements are in decreasing orderreverse(res.begin(), res.end());return res;}int main() {vectorint arr {1, 23, 12, 9, 30, 2, 50};int k 3;vectorint res kLargest(arr, k);for(int ele : res)cout ele ;return 0;}输出50 30 23时间复杂度O(n * log k)由于构建堆需要线性时间因此该方案可在 O(k (nk) Log K) 时间内完成。辅助空间O(k)注意JavaScript 原生实现似乎不支持最小堆因此建议使用快速选择实现。【替代方法】使用快速选择算法其思路是利用快速排序的分区步骤在不重新排序整个数组的情况下找到数组中最大的 k 个元素。在按降序对元素进行排序时分区步骤会重新排列元素将所有大于或等于选定基准元素通常是最后一个元素的元素放在基准元素的左侧将所有小于基准元素的元素放在基准元素的右侧并将基准元素置于其正确的排序位置。每次分区后我们将数组左侧部分包含所有大于或等于基准元素的元素的元素个数与 k进行比较1、左侧元素个数 k这意味着左侧部分的所有元素包括枢轴元素都是最大的 k 个元素。2、左侧元素个数 k这意味着最大的 k 个元素只存在于左侧子数组中因此我们在左侧子数组中递归搜索。3、左侧元素个数小于 k这意味着最大的 k 个元素包含了数组左侧的全部元素以及右侧的部分元素。因此我们将 k 减去左侧已覆盖的元素个数然后在右侧子数组中搜索。快速排序参考c 快速排序 https://blog.csdn.net/hefeng_aspnet/article/details/138489504c语言 快速排序 https://blog.csdn.net/hefeng_aspnet/article/details/138489858C# 快速排序 https://blog.csdn.net/hefeng_aspnet/article/details/138491347java 快速排序 https://blog.csdn.net/hefeng_aspnet/article/details/138491235Python 快速排序 https://blog.csdn.net/hefeng_aspnet/article/details/138491291JavaScript 快速排序 https://blog.csdn.net/hefeng_aspnet/article/details/138491413PHP 快速排序 https://blog.csdn.net/hefeng_aspnet/article/details/138491455替代方法示例代码// C program to find the k largest elements in the array// using partitioning step of quick sort#include iostream#include vector#include algorithmusing namespace std;// Function to partition the array around a pivotint partition(vectorint arr, int left, int right) {// Last element is chosen as a pivot.int pivot arr[right];int i left;for (int j left; j right; j) {// Elements greater than or equal to pivot// are placed in the left side of pivotif (arr[j] pivot) {swap(arr[i], arr[j]);i;}}swap(arr[i], arr[right]);// The correct sorted position of the pivotreturn i;}void quickSelect(vectorint arr, int left, int right, int k) {if (left right) {int pivotIdx partition(arr, left, right);// Count of all elements in the left partint leftCnt pivotIdx - left 1;// If leftCnt is equal to k, then we have// found the k largest elementif (leftCnt k)return;// Search in the left subarrayif (leftCnt k)quickSelect(arr, left, pivotIdx - 1, k);// Reduce the k by number of elements already covered// and search in the right subarrayelsequickSelect(arr, pivotIdx 1, right, k - leftCnt);}}vectorint kLargest(vectorint arr, int k) {int n arr.size();quickSelect(arr, 0, n - 1, k);// First k elements of the array will be the largestvectorint res(arr.begin(), arr.begin() k);// Sort the result in descending ordersort(res.begin(), res.end(), greaterint());return res;}int main() {vectorint arr {1, 23, 12, 9, 30, 2, 50};int k 3;vectorint res kLargest(arr, k);for (int ele : res)cout ele ;return 0;}输出50 30 23时间复杂度最坏情况下为O(n² )平均情况下为 O(n)。辅助空间O(n)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。