如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个数组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 个元素。// JavaScript program to find k largest elements// in an array using sortingfunction kLargest(arr, k) {// sort the given array in descending orderarr.sort((a, b) b - a);// store the first k elements in result arraylet res arr.slice(0, k);return res;}// Driver Codeconst arr [1, 23, 12, 9, 30, 2, 50];const k 3;const res kLargest(arr, k);console.log(res.join( ));输出50 30 23时间复杂度O(n * log n)辅助空间O(1)【预期方法】使用优先级队列最小堆其思路是在遍历数组的过程中每一步都记录下最大的 k 个元素。为此我们使用最小堆。首先将初始的 k 个元素插入最小堆。之后对于每个后续元素我们将其与堆顶元素进行比较。由于最小堆的堆顶元素是这 k 个元素中最小的如果当前元素大于堆顶元素则意味着堆顶元素不再是最大的 k 个元素之一。在这种情况下我们移除堆顶元素并插入更大的元素。完成整个遍历后堆将恰好包含数组中最大的 k 个元素。// JavaScript program to find the k largest elements in the// array using min heapclass MinHeap {constructor() {this.heap [];}// Swap two elements in the heapswap(i, j) {[this.heap[i], this.heap[j]] [this.heap[j], this.heap[i]];}// Heapify up to maintain min heap propertyheapifyUp() {let index this.heap.length - 1;while (index 0) {let parentIndex Math.floor((index - 1) / 2);if (this.heap[parentIndex] this.heap[index]) break;this.swap(parentIndex, index);index parentIndex;}}// Heapify down to maintain min heap propertyheapifyDown() {let index 0;while (2 * index 1 this.heap.length) {let leftChild 2 * index 1;let rightChild 2 * index 2;let smallest leftChild;if (rightChild this.heap.length this.heap[rightChild] this.heap[leftChild]) {smallest rightChild;}if (this.heap[index] this.heap[smallest]) break;this.swap(index, smallest);index smallest;}}// Insert element into the min heappush(val) {this.heap.push(val);this.heapifyUp();}// Remove and return the top element (smallest)pop() {if (this.heap.length 1) return this.heap.pop();let min this.heap[0];this.heap[0] this.heap.pop();this.heapifyDown();return min;}// Get the top element (smallest)top() {return this.heap[0];}// Check if the heap is emptyempty() {return this.heap.length 0;}}// Function to find the k largest elements in the arrayfunction kLargest(arr, k) {// Min Priority Queue (Min-Heap) with first k// elements of the arraylet minH new MinHeap();for (let i 0; i k; i) {minH.push(arr[i]);}// Traverse n - k elementsfor (let i k; i arr.length; 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]);}}let res [];// Min heap will contain only k// largest elementswhile (!minH.empty()) {res.push(minH.pop());}// Reverse the result array, so that all// elements are in decreasing orderres.reverse();return res;}// Driver Codelet arr [1, 23, 12, 9, 30, 2, 50];let k 3;let res kLargest(arr, k);console.log(res.join( ));输出50 30 23时间复杂度O(n * log k)由于构建堆需要线性时间因此该方案可在 O(k (nk) Log K) 时间完成。辅助空间O(k)注意JavaScript 原生实现似乎不支持最小堆因此建议使用快速选择实现。【替代方法】使用快速选择算法其思路是利用快速排序的分区步骤在不重新排序整个数组的情况下找到数组中最大的 k 个元素。c 快速排序c 快速排序QuickSort_快速排序c代码-CSDN博客c语言 快速排序c语言 快速排序QuickSort_分区操作选择最后一个元素作为基准 c语言-CSDN博客python 快速排序Python 快速排序QuickSort_python实现快速排序-CSDN博客c# 快速排序C# 快速排序QuickSort-CSDN博客java 快速排序java 快速排序QuickSort_quicksort java-CSDN博客PHP 快速排序PHP 快速排序QuickSort-CSDN博客JavaScript快速排序JavaScript 快速排序QuickSort-CSDN博客在按降序对元素进行排序时分区步骤会重新排列元素将所有大于或等于选定基准元素通常是最后一个元素的元素放在基准元素的左侧将所有小于基准元素的元素放在基准元素的右侧并将基准元素置于其正确的排序位置。每次分区后我们将数组左侧部分包含所有大于或等于基准元素的元素的元素个数与 k进行比较左侧元素个数 k这意味着左侧部分的所有元素包括枢轴元素都是最大的 k 个元素。左侧元素个数 k这意味着最大的 k 个元素只存在于左侧子数组中因此我们在左侧子数组中递归搜索。左侧元素个数小于 k这意味着最大的 k 个元素包含了数组左侧的全部元素以及右侧的部分元素。因此我们将 k 减去左侧已覆盖的元素个数然后在右侧子数组中搜索。// JavaScript program to find the k largest elements in the array// using partitioning step of quick sort// Function to partition the array around a pivotfunction partition(arr, left, right) {// Last element is chosen as a pivot.let pivot arr[right];let i left;for (let j left; j right; j) {// Elements greater than or equal to pivot are// placed in the left part of pivotif (arr[j] pivot) {[arr[i], arr[j]] [arr[j], arr[i]];i;}}[arr[i], arr[right]] [arr[right], arr[i]];// The correct sorted position of the pivotreturn i;}function quickSelect(arr, left, right, k) {if (left right) {let pivotIdx partition(arr, left, right);// Count of all elements in the left partlet leftCnt pivotIdx - left 1;// If leftCnt is equal to k, then the first// k element of the array will be largestif (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);}}function kLargest(arr, k) {quickSelect(arr, 0, arr.length - 1, k);// First k elements of the array, will be the largestlet res arr.slice(0, k);// Sort the first k elements in descending orderres.sort((a, b) b - a);return res;}// Driver Codeconst arr [1, 23, 12, 9, 30, 2, 50];const k 3;const res kLargest(arr, k);console.log(res.join( ));输出50 30 23时间复杂度最坏情况下为O(n² )平均情况下为 O(n)。辅助空间O(n)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。