Java 找出数组中最大的 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 个元素。// Java program to find k largest elements in an array using// sortingimport java.util.*;class GfG {static ArrayListInteger kLargest(int[] arr, int k) {int n arr.length;// Convert int type to Integer// for sorting with a comparatorInteger[] arrInteger Arrays.stream(arr).boxed().toArray(Integer[]::new);// Sort the array in descending orderArrays.sort(arrInteger, Collections.reverseOrder());// Store the first k elements in result listArrayListInteger res new ArrayList();for (int i 0; i k; i)res.add(arrInteger[i]);return res;}public static void main(String[] args) {int[] arr {1, 23, 12, 9, 30, 2, 50};int k 3;ArrayListInteger res kLargest(arr, k);for (int ele : res)System.out.print(ele );}}输出50 30 23时间复杂度O(n * log n)辅助空间O(1)【预期方法】使用优先级队列最小堆其思路是在遍历数组的过程中每一步都记录下最大的 k 个元素。为此我们使用最小堆。首先将初始的 k 个元素插入最小堆。之后对于每个后续元素我们将其与堆顶元素进行比较。由于最小堆的堆顶元素是这 k 个元素中最小的如果当前元素大于堆顶元素则意味着堆顶元素不再是最大的 k 个元素之一。在这种情况下我们移除堆顶元素并插入更大的元素。完成整个遍历后堆将恰好包含数组中最大的 k 个元素。// Java program to find the k largest elements in the// array using min heapimport java.util.*;class GfG {// Function to find the k largest elements in the arraystatic ArrayListInteger kLargest(int[] arr, int k) {// Min-heap to store the k largest elementsPriorityQueueInteger minHeap new PriorityQueue(k);// Add first k elements to the heapfor (int i 0; i k; i) {minHeap.add(arr[i]);}// Traverse the rest of the arrayfor (int i k; i arr.length; i) {// If current element is larger than// the smallest in heapif (arr[i] minHeap.peek()) {minHeap.poll();minHeap.add(arr[i]);}}// Extract elements from the heapArrayListInteger res new ArrayList();while (!minHeap.isEmpty()) {res.add(minHeap.poll());}// Reverse the list for descending orderCollections.reverse(res);return res;}public static void main(String[] args) {int[] arr {1, 23, 12, 9, 30, 2, 50};int k 3;ArrayListInteger res kLargest(arr, k);for (int ele : res) {System.out.print(ele );}}}输出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 减去左侧已覆盖的元素个数然后在右侧子数组中搜索。// Java program to find the k largest elements in the array// using partitioning step of quick sortimport java.util.*;class GfG {// Function to partition the array around a pivotstatic 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 side of pivotif (arr[j] pivot) {int temp arr[i];arr[i] arr[j];arr[j] temp;i;}}int temp arr[i];arr[i] arr[right];arr[right] temp;// The correct sorted position of the pivotreturn 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 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);}}static ArrayListInteger kLargest(int[] arr, int k) {quickSelect(arr, 0, arr.length - 1, k);ArrayListInteger res new ArrayList();// First k elements of the array, will be the largestfor(int i 0; i k; i)res.add(arr[i]);// Sort the result in descending orderCollections.sort(res, Collections.reverseOrder());return res;}public static void main(String[] args) {int[] arr {1, 23, 12, 9, 30, 2, 50};int k 3;ArrayListInteger res kLargest(arr, k);for (int ele : res)System.out.print(ele );}}输出50 30 23时间复杂度最坏情况下为O(n² )平均情况下为 O(n)。辅助空间O(n)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。