Dada una secuencia infinita de números enteros, encuentre el k-ésimo elemento más grande en cualquier punto del tiempo. Se puede suponer que 1 <= k <= n.
Input: stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...} k = 3 Output: {_, _, 10, 11, 20, 40, 50, 50, ...}
El espacio extra permitido es O(k).
La idea es usar el montón mínimo.
1) Almacene los primeros k elementos en el montón mínimo.
2) Para cada elemento de (k+1)-ésimo a n-ésimo, haga lo siguiente.
……a) Imprime la raíz del montón.
……b) Si el elemento actual es más que la raíz del montón, extraiga la raíz e inserte
CPP
// CPP program to find k-th largest element in a // stream after every insertion. #include <bits/stdc++.h> using namespace std; int kthLargest(int stream[], int n, int k) { // Create a min heap and store first k-1 elements // of stream into priority_queue<int, vector<int>, greater<int> > pq; // Push first k elements and print "_" (k-1) times for (int i=0; i<k-1; i++) { pq.push(stream[i]); cout << "_ "; } pq.push(stream[k-1]); for (int i=k; i<n; i++) { // We must insert last element before we // decide last k-th largest output. cout << pq.top() << " "; if (stream[i] > pq.top()) { pq.pop(); pq.push(stream[i]); } } // Print last k-th largest element (after // (inserting last element) cout << pq.top(); } // Driver code int main() { int arr[] = {10, 20, 11, 70, 50, 40, 100, 55}; int k = 3; int n = sizeof(arr)/sizeof(arr[0]); kthLargest(arr, n, k); return 0; }
Java
// Java Program for the above approach import java.util.*; class GFG { static void kthLargest(int stream[], int n, int k) { // Create a min heap and store first k-1 elements // of stream into Vector<Integer> pq = new Vector<Integer>(n); // Push first k elements and print "_" (k-1) times for (int i = 0; i < k - 1; i++) { pq.add(stream[i]); System.out.print("_ "); } pq.add(stream[k - 1]); for (int i = k; i < n; i++) { // We must insert last element before we // decide last k-th largest output. Collections.sort(pq); System.out.print(pq.get(0) + " "); if (stream[i] > pq.get(0)) { pq.remove(0); pq.add(stream[i]); } } // Print last k-th largest element (after // (inserting last element) Collections.sort(pq); System.out.print(pq.get(0)); } // Driver code public static void main(String[] args) { int arr[] = {10, 20, 11, 70, 50, 40, 100, 55}; int k = 3; int n = arr.length; kthLargest(arr, n, k); } } // This code is contributed by divyeshrabadiya07.
Python3
## Python Program for the above approach import heapq def kthLargest(stream, n, k): # Create a min heap and store first k-1 elements # of stream into pq = [] # Push first k elements and print "_" (k-1) times for i in range(k - 1): pq.append(stream[i]) print("_ ", end = "") pq.append(stream[k - 1]) # creating min heap and maintaining the heap # property heapq.heapify(pq) for i in range(k,n): # We must insert last element before we # decide last k-th largest output. print(pq[0],end=" ") if (stream[i]>pq[0]): #deleting the last element from the min heap pq[0]=pq[-1] pq.pop() pq.append(stream[i]) heapq.heapify(pq); ## Print last k-th largest element (after # (inserting last element) print(pq[0]) # Driver code arr = [10, 20, 11, 70, 50, 40, 100, 55] k = 3 n = len(arr) kthLargest(arr, n, k) '''Code is contributed by Rajat Kumar'''
C#
// C# program to find k-th largest element in a // stream after every insertion. using System; using System.Collections.Generic; class GFG { static void kthLargest(int[] stream, int n, int k) { // Create a min heap and store first k-1 elements // of stream into List<int> pq = new List<int>(); // Push first k elements and print "_" (k-1) times for (int i = 0; i < k - 1; i++) { pq.Add(stream[i]); Console.Write("_ "); } pq.Add(stream[k - 1]); for (int i = k; i < n; i++) { // We must insert last element before we // decide last k-th largest output. pq.Sort(); Console.Write(pq[0] + " "); if (stream[i] > pq[0]) { pq.RemoveAt(0); pq.Add(stream[i]); } } // Print last k-th largest element (after // (inserting last element) pq.Sort(); Console.Write(pq[0]); } // Driver code static void Main() { int[] arr = {10, 20, 11, 70, 50, 40, 100, 55}; int k = 3; int n = arr.Length; kthLargest(arr, n, k); } } // This code is contributed by divyesh072019.
Javascript
<script> // JavaScript program to find k-th largest element in a // stream after every insertion. function kthLargest(stream, n, k) { // Create a min heap and store first k-1 elements // of stream into let pq = new Array(); // Push first k elements and print "_" (k-1) times for (let i = 0; i < k - 1; i++) { pq.push(stream[i]); document.write("_ "); } pq.push(stream[k - 1]); for (let i = k; i < n; i++) { // We must insert last element before we // decide last k-th largest output. pq.sort((a, b) => a - b); document.write(pq[0] + " "); if (stream[i] > pq[0]) { pq.shift(0); pq.push(stream[i]); } } // Print last k-th largest element (after // (inserting last element) pq.sort((a, b) => a - b); document.write(pq[0]); } // Driver code let arr = [10, 20, 11, 70, 50, 40, 100, 55]; let k = 3; let n = arr.length; kthLargest(arr, n, k); // This code is contributed by _saurabh_jaiswal </script>
_ _ 10 11 20 40 50 55
Si el flujo contiene elementos de tipos no primitivos, podemos definir nuestra propia función de compactador y crear una cola de prioridad en consecuencia.
Publicación traducida automáticamente
Artículo escrito por sahilshelangia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA