问题: 编写一个高效的程序来打印数组中k个最大的元素。数组中的元素可以是任意顺序。 例如，如果给定的数组是[1,23,12,9,30,2,50]，并且要求您输入最大的3个元素，即k=3，那么您的程序应该打印50,30和23。
null
方法1（使用气泡k次） 感谢Shailendra提出这种方法。 1） 修改 气泡排序 最多运行外部循环k次。 2） 打印在步骤1中获得的数组的最后k个元素。 时间复杂度：O（n*k）
像冒泡排序，其他排序算法 选择排序 也可以修改以获得k个最大元素。
方法2（使用临时数组） K来自arr的最大元素[0..n-1]
1） 将前k个元素存储在临时数组temp[0..k-1]中。 2） 在temp[]中找到最小的元素，让最小的元素为 闵 . 3-a）每个元素 十、 在arr[k]到arr[n-1]之间。 O（n-k） 如果 十、 大于最小值，然后移除 闵 从temp[]插入 十、 . 3-b）然后，确定新的 闵 来自temp[]。 O（k） 4） 打印最后的k元素 温度[]
时间复杂度：O（（n-k）*k）。如果我们想对输出进行排序，那么O（（n-k）*k+k*log（k）） 感谢nesamani1822提出这种方法。
方法3（使用排序） 1） 按O（n*log（n））降序排列元素 2） 打印排序数组O（k）的前k个数字。
以下是上述措施的实施情况。
C++
// C++ code for k largest elements in an array #include <bits/stdc++.h> using namespace std; void kLargest( int arr[], int n, int k) { // Sort the given array arr in reverse // order. sort(arr, arr + n, greater< int >()); // Print the first kth largest elements for ( int i = 0; i < k; i++) cout << arr[i] << " " ; } // driver program int main() { int arr[] = { 1, 23, 12, 9, 30, 2, 50 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; kLargest(arr, n, k); } // This article is contributed by Chhavi |
JAVA
// Java code for k largest elements in an array import java.util.Arrays; import java.util.Collections; import java.util.ArrayList; class GFG { public static void kLargest(Integer[] arr, int k) { // Sort the given array arr in reverse order // This method doesn't work with primitive data // types. So, instead of int, Integer type // array will be used Arrays.sort(arr, Collections.reverseOrder()); // Print the first kth largest elements for ( int i = 0 ; i < k; i++) System.out.print(arr[i] + " " ); } //This code is contributed by Niraj Dubey public static ArrayList<Integer> kLargest( int [] arr, int k) { //Convert using stream Integer[] obj_array = Arrays.stream( arr ).boxed().toArray( Integer[] :: new ); Arrays.sort(obj_array, Collections.reverseOrder()); ArrayList<Integer> list = new ArrayList<>(k); for ( int i = 0 ; i < k; i++) list.add(obj_array[i]); return list; } public static void main(String[] args) { Integer arr[] = new Integer[] { 1 , 23 , 12 , 9 , 30 , 2 , 50 }; int k = 3 ; kLargest(arr, k); //This code is contributed by Niraj Dubey //What if primitive datatype array is passed and wanted to return in ArrayList<Integer> int [] prim_array = { 1 , 23 , 12 , 9 , 30 , 2 , 50 }; System.out.print(kLargest(prim_array, k)); } } // This code is contributed by Kamal Rawal |
python
''' Python3 code for k largest elements in an array''' def kLargest(arr, k): # Sort the given array arr in reverse # order. arr.sort(reverse = True ) # Print the first kth largest elements for i in range (k): print (arr[i], end = " " ) # Driver program arr = [ 1 , 23 , 12 , 9 , 30 , 2 , 50 ] # n = len(arr) k = 3 kLargest(arr, k) # This code is contributed by shreyanshi_arun. |
C#
// C# code for k largest elements in an array using System; class GFG { public static void kLargest( int [] arr, int k) { // Sort the given array arr in reverse order // This method doesn't work with primitive data // types. So, instead of int, Integer type // array will be used Array.Sort(arr); Array.Reverse(arr); // Print the first kth largest elements for ( int i = 0; i < k; i++) Console.Write(arr[i] + " " ); } // Driver code public static void Main(String[] args) { int [] arr = new int [] { 1, 23, 12, 9, 30, 2, 50 }; int k = 3; kLargest(arr, k); } } // This code contributed by Rajput-Ji |
PHP
<?php // PHP code for k largest // elements in an array function kLargest(& $arr , $n , $k ) { // Sort the given array arr // in reverse order. rsort( $arr ); // Print the first kth // largest elements for ( $i = 0; $i < $k ; $i ++) echo $arr [ $i ] . " " ; } // Driver Code $arr = array (1, 23, 12, 9, 30, 2, 50); $n = sizeof( $arr ); $k = 3; kLargest( $arr , $n , $k ); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // JavaScript code for k largest // elements in an array function kLargest(arr, n, k) { // Sort the given array arr in reverse // order. arr.sort((a, b) => b - a); // Print the first kth largest elements for (let i = 0; i < k; i++) document.write(arr[i] + " " ); } // driver program let arr = [ 1, 23, 12, 9, 30, 2, 50 ]; let n = arr.length; let k = 3; kLargest(arr, n, k); // This code is contributed by Manoj. </script> |
输出
50 30 23
时间复杂性： O（n*log（n））
方法4（使用最大堆） 1） 在O（n）中构建最大堆树 2） 使用Extract Max k times从Max Heap O（k*log（n））中获取k个最大元素
时间复杂性： O（n+k*log（n））
方法5（使用顺序统计） 1） 使用顺序统计算法查找第k个最大元素。请 请参阅最坏情况下线性时间的主题选择 O（n） 2） 使用 快速排序 分区算法是围绕第k个最大数O（n）进行分区。 3） 将k-1元素（大于第k个最大元素的元素）排序为O（k*log（k））。仅当需要排序输出时才需要此步骤。
时间复杂性： O（n）如果我们不需要排序的输出，否则O（n+k*log（k）） 感谢Shilpi提出前两种方法。
方法6（使用最小堆） 该方法主要是对方法1的优化。不要使用temp[]数组，而是使用Min Heap。 1） 构建给定数组的前k个元素（arr[0]到arr[k-1]）的最小堆MH。 O （k*log（k）） 2） 对于每个元素，在第k个元素（arr[k]到arr[n-1]）之后，将其与MH的根进行比较。 ……a）如果元素大于根，则将其设为根并调用 希皮菲 对于MH ……b）否则忽略它。 //第二步是O（（n-k）*log（k）） 3） 最后，MH有k个最大元素，MH的根是第k个最大元素。 时间复杂度：O（k*log（k）+（n-k）*log（k）），无排序输出。如果需要排序输出，那么O（k*log（k）+（n-k）*log（k）+k*log（k）），所以总体上是O（k*log（k）+（n-k）*log（k））
上述所有方法也可用于查找第k个最大（或最小）元素。
C++
#include <iostream> using namespace std; // Swap function to interchange // the value of variables x and y int swap( int & x, int & y) { int temp = x; x = y; y = temp; } // Min Heap Class // arr holds reference to an integer // array size indicate the number of // elements in Min Heap class MinHeap { int size; int * arr; public : // Constructor to initialize the size and arr MinHeap( int size, int input[]); // Min Heapify function, that assumes that // 2*i+1 and 2*i+2 are min heap and fix the // heap property for i. void heapify( int i); // Build the min heap, by calling heapify // for all non-leaf nodes. void buildHeap(); }; // Constructor to initialize data // members and creating mean heap MinHeap::MinHeap( int size, int input[]) { // Initializing arr and size this ->size = size; this ->arr = input; // Building the Min Heap buildHeap(); } // Min Heapify function, that assumes // 2*i+1 and 2*i+2 are min heap and // fix min heap property for i void MinHeap::heapify( int i) { // If Leaf Node, Simply return if (i >= size / 2) return ; // variable to store the smallest element // index out of i, 2*i+1 and 2*i+2 int smallest; // Index of left node int left = 2 * i + 1; // Index of right node int right = 2 * i + 2; // Select minimum from left node and // current node i, and store the minimum // index in smallest variable smallest = arr[left] < arr[i] ? left : i; // If right child exist, compare and // update the smallest variable if (right < size) smallest = arr[right] < arr[smallest] ? right : smallest; // If Node i violates the min heap // property, swap current node i with // smallest to fix the min-heap property // and recursively call heapify for node smallest. if (smallest != i) { swap(arr[i], arr[smallest]); heapify(smallest); } } // Build Min Heap void MinHeap::buildHeap() { // Calling Heapify for all non leaf nodes for ( int i = size / 2 - 1; i >= 0; i--) { heapify(i); } } void FirstKelements( int arr[], int size, int k){ // Creating Min Heap for given // array with only k elements MinHeap* m = new MinHeap(k, arr); // Loop For each element in array // after the kth element for ( int i = k; i < size; i++) { // if current element is smaller // than minimum element, do nothing // and continue to next element if (arr[0] > arr[i]) continue ; // Otherwise Change minimum element to // current element, and call heapify to // restore the heap property else { arr[0] = arr[i]; m->heapify(0); } } // Now min heap contains k maximum // elements, Iterate and print for ( int i = 0; i < k; i++) { cout << arr[i] << " " ; } } // Driver Program int main() { int arr[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 }; int size = sizeof (arr) / sizeof (arr[0]); // Size of Min Heap int k = 3; FirstKelements(arr,size,k); return 0; } // This code is contributed by Ankur Goel |
JAVA
import java.io.*; import java.util.*; class GFG{ public static void FirstKelements( int arr[], int size, int k) { // Creating Min Heap for given // array with only k elements // Create min heap with priority queue PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for ( int i = 0 ; i < k; i++) { minHeap.add(arr[i]); } // Loop For each element in array // after the kth element for ( int i = k; i < size; i++) { // If current element is smaller // than minimum ((top element of // the minHeap) element, do nothing // and continue to next element if (minHeap.peek() > arr[i]) continue ; // Otherwise Change minimum element // (top element of the minHeap) to // current element by polling out // the top element of the minHeap else { minHeap.poll(); minHeap.add(arr[i]); } } // Now min heap contains k maximum // elements, Iterate and print Iterator iterator = minHeap.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + " " ); } } // Driver code public static void main (String[] args) { int arr[] = { 11 , 3 , 2 , 1 , 15 , 5 , 4 , 45 , 88 , 96 , 50 , 45 }; int size = arr.length; // Size of Min Heap int k = 3 ; FirstKelements(arr, size, k); } } // This code is contributed by Vansh Sethi |
蟒蛇3
def FirstKelements(arr,size,k): # Creating Min Heap for given # array with only k elements # Create min heap with priority queue minHeap = [] for i in range (k): minHeap.append(arr[i]) # Loop For each element in array # after the kth element for i in range (k, size): minHeap.sort() # If current element is smaller # than minimum ((top element of # the minHeap) element, do nothing # and continue to next element if (minHeap[ 0 ] > arr[i]): continue # Otherwise Change minimum element # (top element of the minHeap) to # current element by polling out # the top element of the minHeap else : minHeap.pop( 0 ) minHeap.append(arr[i]) # Now min heap contains k maximum # elements, Iterate and print for i in minHeap: print (i, end = " " ) # Driver code arr = [ 11 , 3 , 2 , 1 , 15 , 5 , 4 , 45 , 88 , 96 , 50 , 45 ] size = len (arr) # Size of Min Heap k = 3 FirstKelements(arr, size, k) # This code is contributed by avanitrachhadiya2155 |
C#
using System; using System.Collections.Generic; public class GFG { public static void FirstKelements( int []arr, int size, int k) { // Creating Min Heap for given // array with only k elements // Create min heap with priority queue List< int > minHeap = new List< int >(); for ( int i = 0; i < k; i++) { minHeap.Add(arr[i]); } // Loop For each element in array // after the kth element for ( int i = k; i < size; i++) { minHeap.Sort(); // If current element is smaller // than minimum ((top element of // the minHeap) element, do nothing // and continue to next element if (minHeap[0] > arr[i]) continue ; // Otherwise Change minimum element // (top element of the minHeap) to // current element by polling out // the top element of the minHeap else { minHeap.RemoveAt(0); minHeap.Add(arr[i]); } } // Now min heap contains k maximum // elements, Iterate and print foreach ( int i in minHeap) { Console.Write(i + " " ); } } // Driver code public static void Main(String[] args) { int []arr = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 }; int size = arr.Length; // Size of Min Heap int k = 3; FirstKelements(arr, size, k); } } // This code is contributed by aashish1995. |
Javascript
<script> function FirstKelements(arr , size , k) { // Creating Min Heap for given // array with only k elements // Create min heap with priority queue var minHeap = []; for ( var i = 0; i < k; i++) { minHeap.push(arr[i]); } // Loop For each element in array // after the kth element for ( var i = k; i < size; i++) { minHeap.sort((a,b)=>a-b); // If current element is smaller // than minimum ((top element of // the minHeap) element, do nothing // and continue to next element if (minHeap[minHeap.length-3] > arr[i]) continue ; // Otherwise Change minimum element // (top element of the minHeap) to // current element by polling out // the top element of the minHeap else { minHeap.reverse(); minHeap.pop(); minHeap.reverse(); minHeap.push(arr[i]); } } // Now min heap contains k maximum // elements, Iterate and print for ( var iterator of minHeap) { document.write(iterator + " " ); } } // Driver code var arr = [11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45]; var size = arr.length; // Size of Min Heap var k = 3; FirstKelements(arr, size, k); // This code is contributed by gauravrajput1 </script> |
输出
50 88 96
方法7（使用快速排序分区算法）：
- 选择一个轴号。
- 如果K小于pivot_指数，则重复该步骤。
- 如果K==pivot_Index：打印数组（低到pivot以获得K个最小元素，以及（n-pivot_Index）到n以获得K个最大元素）
- 如果K>pivot_Index：对右侧部分重复上述步骤。
我们可以使用random（）函数来改进标准的快速排序算法。我们可以随机选择枢轴元素，而不是使用枢轴元素作为最后一个元素。该版本最坏情况下的时间复杂度为O（n2），平均时间复杂度为O（n）。
以下是上述算法的实现：
C++
#include <bits/stdc++.h> using namespace std; //picks up last element between start and end int findPivot( int a[], int start, int end) { // Selecting the pivot element int pivot = a[end]; // Initially partition-index will be // at starting int pIndex = start; for ( int i = start; i < end; i++) { // If an element is lesser than pivot, swap it. if (a[i] <= pivot) { swap(a[i], a[pIndex]); // Incrementing pIndex for further // swapping. pIndex++; } } // Lastly swapping or the // correct position of pivot swap(a[pIndex], a[end]); return pIndex; } //THIS PART OF CODE IS CONTRIBUTED BY - rjrachit //Picks up random pivot element between start and end int findRandomPivot( int arr[], int start, int end) { int n = end - start + 1; // Selecting the random pivot index int pivotInd = random()%n; swap(arr[end],arr[start+pivotInd]); int pivot = arr[end]; //initialising pivoting point to start index pivotInd = start; for ( int i = start; i < end; i++) { // If an element is lesser than pivot, swap it. if (arr[i] <= pivot) { swap(arr[i], arr[pivotInd]); // Incrementing pivotIndex for further // swapping. pivotInd++; } } // Lastly swapping or the // correct position of pivot swap(arr[pivotInd], arr[end]); return pivotInd; } //THIS PART OF CODE IS CONTRIBUTED BY - rjrachit void SmallestLargest( int a[], int low, int high, int k, int n) { if (low == high) return ; else { int pivotIndex = findRandomPivot(a, low, high); if (k == pivotIndex) { cout << k << " smallest elements are : " ; for ( int i = 0; i < pivotIndex; i++) cout << a[i] << " " ; cout << endl; cout << k << " largest elements are : " ; for ( int i = (n - pivotIndex); i < n; i++) cout << a[i] << " " ; } else if (k < pivotIndex) SmallestLargest(a, low, pivotIndex - 1, k, n); else if (k > pivotIndex) SmallestLargest(a, pivotIndex + 1, high, k, n); } } // Driver Code int main() { int a[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 }; int n = sizeof (a) / sizeof (a[0]); int low = 0; int high = n - 1; // Lets assume k is 3 int k = 4; // Function Call SmallestLargest(a, low, high, k, n); return 0; } |
输出
3 smallest elements are : 3 2 1 3 largest elements are : 96 50 88
如果您发现上述任何解释/算法不正确，请写下评论，或者找到更好的方法来解决相同的问题。 参考资料： http://en.wikipedia.org/wiki/Selection_algorithm
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
