给定一个无限的整数流，在任意时间点找到第k大元素。 例子：
null
Input:stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...}k = 3Output: {_, _, 10, 11, 20, 40, 50, 50, ...}
允许的额外空间为O（k）。
在下面的文章中，我们讨论了寻找数组中第k大元素的不同方法。 未排序数组中第K个最小/最大元素|集1 未排序数组中第K个最小/最大元素|集2（预期线性时间） 未排序数组中第K个最小/最大元素|集3（最坏情况线性时间） 这里我们有一个流而不是整个数组，我们只允许存储k个元素。
A. 简单解决方案 就是保持一个大小为k的数组。这个想法是保持数组的排序，以便在O（1）时间内找到第k个最大的元素（如果数组按递增顺序排序，我们只需要返回数组的第一个元素） 如何处理流中的新元素？ 对于流中的每个新元素，检查新元素是否小于当前第k个最大元素。如果是，则忽略它。如果否，则从数组中移除最小的元素，并按排序顺序插入新元素。处理新元素的时间复杂度为O（k）。
A. 更好的解决方案 就是使用大小为k的自平衡二叉搜索树。第k个最大元素可以在O（Logk）时间内找到。 如何处理流中的新元素？ 对于流中的每个新元素，检查新元素是否小于当前第k个最大元素。如果是，则忽略它。如果没有，则从树中删除最小的元素并插入新元素。处理新元素的时间复杂度为O（Logk）。
一 有效解决方案 就是使用大小为k的最小堆来存储流中最大的k个元素。第k大元素总是在根上，可以在O（1）时间内找到。 如何处理流中的新元素？ 将新元素与堆的根进行比较。如果新元素较小，则忽略它。否则，用新元素替换root，并为修改后的堆的根调用heapify。求第k大元素的时间复杂度为O（Logk）。
CPP
// A C++ program to find k'th // smallest element in a stream #include <climits> #include <iostream> using namespace std; // Prototype of a utility function // to swap two integers void swap( int * x, int * y); // A class for Min Heap class MinHeap { int * harr; // pointer to array of elements in heap int capacity; // maximum possible size of min heap int heap_size; // Current number of elements in min heap public : MinHeap( int a[], int size); // Constructor void buildHeap(); void MinHeapify( int i); // To minheapify subtree rooted with index i int parent( int i) { return (i - 1) / 2; } int left( int i) { return (2 * i + 1); } int right( int i) { return (2 * i + 2); } int extractMin(); // extracts root (minimum) element int getMin() { return harr[0]; } // to replace root with new node x and heapify() new // root void replaceMin( int x) { harr[0] = x; MinHeapify(0); } }; MinHeap::MinHeap( int a[], int size) { heap_size = size; harr = a; // store address of array } void MinHeap::buildHeap() { int i = (heap_size - 1) / 2; while (i >= 0) { MinHeapify(i); i--; } } // Method to remove minimum element // (or root) from min heap int MinHeap::extractMin() { if (heap_size == 0) return INT_MAX; // Store the minimum value. int root = harr[0]; // If there are more than 1 items, // move the last item to // root and call heapify. if (heap_size > 1) { harr[0] = harr[heap_size - 1]; MinHeapify(0); } heap_size--; return root; } // A recursive method to heapify a subtree with root at // given index This method assumes that the subtrees are // already heapified void MinHeap::MinHeapify( int i) { int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l] < harr[i]) smallest = l; if (r < heap_size && harr[r] < harr[smallest]) smallest = r; if (smallest != i) { swap(&harr[i], &harr[smallest]); MinHeapify(smallest); } } // A utility function to swap two elements void swap( int * x, int * y) { int temp = *x; *x = *y; *y = temp; } // Function to return k'th largest element from input stream void kthLargest( int k) { // count is total no. of elements in stream seen so far int count = 0, x; // x is for new element // Create a min heap of size k int * arr = new int [k]; MinHeap mh(arr, k); while (1) { // Take next element from stream cout << "Enter next element of stream " ; cin >> x; // Nothing much to do for first k-1 elements if (count < k - 1) { arr[count] = x; count++; } else { // If this is k'th element, then store it // and build the heap created above if (count == k - 1) { arr[count] = x; mh.buildHeap(); } else { // If next element is greater than // k'th largest, then replace the root if (x > mh.getMin()) mh.replaceMin(x); // replaceMin calls // heapify() } // Root of heap is k'th largest element cout << "K'th largest element is " << mh.getMin() << endl; count++; } } } // Driver program to test above methods int main() { int k = 3; cout << "K is " << k << endl; kthLargest(k); return 0; } |
JAVA
// Java program for the above approach import java.io.*; import java.util.*; class GFG { /* using min heap DS how data are stored in min Heap DS 1 2 3 if k==3 , then top element of heap itself the kth largest largest element */ static PriorityQueue<Integer> min; static int k; static List<Integer> getAllKthNumber( int arr[]) { // list to store kth largest number List<Integer> list = new ArrayList<>(); // one by one adding values to the min heap for ( int val : arr) { // if the heap size is less than k , we add to // the heap if (min.size() < k) min.add(val); /* otherwise , first we compare the current value with the min heap TOP value if TOP val > current element , no need to remove TOP , bocause it will be the largest kth element anyhow else we need to update the kth largest element by removing the top lowest element */ else { if (val > min.peek()) { min.poll(); min.add(val); } } // if heap size >=k we add // kth largest element // otherwise -1 if (min.size() >= k) list.add(min.peek()); else list.add(- 1 ); } return list; } // Driver Code public static void main(String[] args) { min = new PriorityQueue<>(); k = 4 ; int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; List<Integer> res = getAllKthNumber(arr); for ( int x : res) System.out.print(x + " " ); } // This code is Contributed by Pradeep Mondal P } |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { /* using min heap DS how data are stored in min Heap DS 1 2 3 if k==3 , then top element of heap itself the kth largest largest element */ static Queue< int > min; static int k; static List< int > getAllKthNumber( int []arr) { // list to store kth largest number List< int > list = new List< int >(); // one by one adding values to the min heap foreach ( int val in arr) { // if the heap size is less than k , we add to // the heap if (min.Count < k) min.Enqueue(val); /* otherwise , first we compare the current value with the min heap TOP value if TOP val > current element , no need to remove TOP , bocause it will be the largest kth element anyhow else we need to update the kth largest element by removing the top lowest element */ else { if (val > min.Peek()) { min.Dequeue(); min.Enqueue(val); } } // if heap size >=k we add // kth largest element // otherwise -1 if (min.Count >= k) list.Add(min.Peek()); else list.Add(-1); } return list; } // Driver Code public static void Main(String[] args) { min = new Queue< int >(); k = 4; int []arr = { 1, 2, 3, 4, 5, 6 }; List< int > res = getAllKthNumber(arr); foreach ( int x in res) Console.Write(x + " " ); } } // This code is contributed by shikhasingrajput |
输出：
K is 3Enter next element of stream 23Enter next element of stream 10Enter next element of stream 15K'th largest element is 10Enter next element of stream 70K'th largest element is 15Enter next element of stream 5K'th largest element is 15Enter next element of stream 80K'th largest element is 23Enter next element of stream 100K'th largest element is 70Enter next element of streamCTRL + C pressed
使用优先级队列的实现：
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; vector< int > kthLargest( int k, int arr[], int n) { vector< int > ans(n); // Creating a min-heap using priority queue priority_queue< int , vector< int >, greater< int > > pq; // Iterating through each element for ( int i = 0; i < n; i++) { // If size of priority // queue is less than k if (pq.size() < k) pq.push(arr[i]); else { if (arr[i] > pq.top()) { pq.pop(); pq.push(arr[i]); } } // If size is less than k if (pq.size() < k) ans[i] = -1; else ans[i] = pq.top(); } return ans; } // Driver Code int main() { int n = 6; int arr[n] = { 1, 2, 3, 4, 5, 6 }; int k = 4; // Function call vector< int > v = kthLargest(k, arr, n); for ( auto it : v) cout << it << " " ; return 0; } |
JAVA
// Java program for the above approach import java.util.*; class GFG{ static int [] kthLargest( int k, int arr[], int n) { int []ans = new int [n]; // Creating a min-heap using priority queue PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->a-b); // Iterating through each element for ( int i = 0 ; i < n; i++) { // If size of priority // queue is less than k if (pq.size() < k) pq.add(arr[i]); else { if (arr[i] > pq.peek()) { pq.remove(); pq.add(arr[i]); } } // If size is less than k if (pq.size() < k) ans[i] = - 1 ; else ans[i] = pq.peek(); } return ans; } // Driver Code public static void main(String[] args) { int n = 6 ; int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; int k = 4 ; // Function call int [] v = kthLargest(k, arr, n); for ( int it : v) System.out.print(it+ " " ); } } // This code is contributed by shikhasingrajput |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG{ static int [] kthLargest( int k, int []arr, int n) { int []ans = new int [n]; // Creating a min-heap using priority queue List< int > pq = new List< int >(); // Iterating through each element for ( int i = 0; i < n; i++) { // If size of priority // queue is less than k if (pq.Count < k) pq.Add(arr[i]); else { if (arr[i] > pq[0]) { pq.Sort(); pq.RemoveAt(0); pq.Add(arr[i]); } } // If size is less than k if (pq.Count < k) ans[i] = -1; else ans[i] = pq[0]; } return ans; } // Driver Code public static void Main(String[] args) { int n = 6; int []arr = { 1, 2, 3, 4, 5, 6 }; int k = 4; // Function call int [] v = kthLargest(k, arr, n); foreach ( int it in v) Console.Write(it+ " " ); } } // This code contributed by shikhasingrajput |
输出
-1 -1 -1 1 2 3
本文由 希瓦姆·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
