)
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
给定一个数组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 sorting
function kLargest(arr, k) {
// sort the given array in descending order
arr.sort((a, b) => b - a);
// store the first k elements in result array
let res = arr.slice(0, k);
return res;
}
// Driver Code
const 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 heap
class MinHeap {
constructor() {
this.heap = [];
}
// Swap two elements in the heap
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
// Heapify up to maintain min heap property
heapifyUp() {
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 property
heapifyDown() {
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 heap
push(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 empty
empty() {
return this.heap.length === 0;
}
}
// Function to find the k largest elements in the array
function kLargest(arr, k) {
// Min Priority Queue (Min-Heap) with first k
// elements of the array
let minH = new MinHeap();
for (let i = 0; i < k; i++) {
minH.push(arr[i]);
}
// Traverse n - k elements
for (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 elements
while (!minH.empty()) {
res.push(minH.pop());
}
// Reverse the result array, so that all
// elements are in decreasing order
res.reverse();
return res;
}
// Driver Code
let 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 pivot
function 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 pivot
if (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 pivot
return i;
}
function quickSelect(arr, left, right, k) {
if (left <= right) {
let pivotIdx = partition(arr, left, right);
// Count of all elements in the left part
let leftCnt = pivotIdx - left + 1;
// If leftCnt is equal to k, then the first
// k element of the array will be largest
if (leftCnt === k)
return;
// Search in the left subarray
if (leftCnt > k)
quickSelect(arr, left, pivotIdx - 1, k);
// Reduce the k by number of elements already covered
// and search in the right subarray
else
quickSelect(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 largest
let res = arr.slice(0, k);
// Sort the first k elements in descending order
res.sort((a, b) => b - a);
return res;
}
// Driver Code
const 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)
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
