企业官网建设流程全解析

目录

例如

【朴素方法】使用排序

朴素方法示例代码

【预期方法】使用优先级队列（最小堆）

预期方法示例代码

【替代方法】使用快速选择算法

快速排序参考

替代方法示例代码

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。

给定一个数组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

using System;
using System.Collections.Generic;
using System.Linq;

class GfG {
static List<int> kLargest(int[] arr, int k) {

// sort the given array in descending order
Array.Sort(arr, (a, b) => b.CompareTo(a));

// store the first k elements in result list
List<int> res = new List<int>();
for (int i = 0; i < k; i++) {
res.Add(arr[i]);
}
return res;
}

static void Main() {
int[] arr = {1, 23, 12, 9, 30, 2, 50};
int k = 3;

List<int> res = kLargest(arr, k);
foreach (int ele in res)
Console.Write(ele + " ");
}
}

输出
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

using System;
using System.Collections.Generic;

class GfG {

// Function to find the k largest elements in the array
static List<int> kLargest(int[] arr, int k) {

// Min-heap using a SortedSet
SortedSet<int> minH = new SortedSet<int>();

// Insert the first k elements into the min-heap
for (int i = 0; i < k; i++) {
minH.Add(arr[i]);
}

// Process the remaining elements
for (int i = k; i < arr.Length; i++) {

// If the current element is larger
// than the smallest in the heap
if (arr[i] > minH.Min) {
minH.Remove(minH.Min);
minH.Add(arr[i]);
}
}

// Extract k largest elements from the heap
List<int> res = new List<int>(minH);

// Reverse the result array to get
// elements in decreasing order
res.Sort((a, b) => b.CompareTo(a));
return res;
}

static void Main() {
int[] arr = { 1, 23, 12, 9, 30, 2, 50 };
int k = 3;

List<int> res = kLargest(arr, k);
foreach (int ele in res)
Console.Write(ele + " ");
}
}

输出
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++ 快速排序 c++ 快速排序（QuickSort）_快速排序c++代码-CSDN博客
c语言 快速排序 c语言 快速排序（QuickSort）_分区操作选择最后一个元素作为基准 c语言-CSDN博客
C# 快速排序 C# 快速排序（QuickSort）-CSDN博客
java 快速排序 java 快速排序（QuickSort）-CSDN博客
Python 快速排序 Python 快速排序（QuickSort）_python实现快速排序-CSDN博客
JavaScript 快速排序 JavaScript 快速排序（QuickSort）-CSDN博客
PHP 快速排序 PHP 快速排序（QuickSort）-CSDN博客

替代方法示例代码

// C# program to find the k largest elements in the array
// using partitioning step of quick sort

using System;
using System.Collections.Generic;

class GfG {

// Function to partition the array around a pivot
static int partition(int[] 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 part of pivot
if (arr[j] >= pivot) {
swap(arr, i, j);
i++;
}
}

swap(arr, i, right);

// The correct sorted position of the pivot
return i;
}

static void quickSelect(int[] arr, int left, int right, int k) {
if (left <= right) {
int pivotIdx = partition(arr, left, right);

// Count of all elements in the left part
int leftCnt = pivotIdx - left + 1;

// If leftCnt is equal to k, then we have
// found the k largest element
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);
}
}

static List<int> kLargest(int[] arr, int k) {
quickSelect(arr, 0, arr.Length - 1, k);

// First k elements of the array will be the largest
List<int> res = new List<int>();
for (int i = 0; i < k; i++) {
res.Add(arr[i]);
}

// Sort the list in descending order
res.Sort((a, b) => b.CompareTo(a));
return res;
}

static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

static void Main() {
int[] arr = {1, 23, 12, 9, 30, 2, 50};
int k = 3;

List<int> res = kLargest(arr, k);
foreach (int ele in res)
Console.Write(ele + " ");
}
}

输出
50 30 23

时间复杂度：最坏情况下为O(n² )（平均情况下为 O(n)）。

辅助空间：O(n)

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。