Dada una secuencia infinita de números enteros, encuentre el k-ésimo elemento más grande en cualquier punto del tiempo.
Ejemplo:
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).
Hemos discutido diferentes enfoques para encontrar el k-ésimo elemento más grande en una array en las siguientes publicaciones.
K’th elemento más pequeño/más grande en array no ordenada | Establecer 1
k’ésimo elemento más pequeño/más grande en array sin clasificar | Conjunto 2 (Tiempo lineal esperado)
K’th Elemento más pequeño/más grande en array no ordenada | Conjunto 3 (Tiempo lineal en el peor de los casos)
Aquí tenemos una secuencia en lugar de una array completa y podemos almacenar solo k elementos.
Una solución simple es mantener una array de tamaño k. La idea es mantener la array ordenada de modo que el k-ésimo elemento más grande se pueda encontrar en el tiempo O(1) (solo necesitamos devolver el primer elemento de la array si la array está ordenada en orden creciente)
Cómo procesar un nuevo elemento de ¿corriente?
Para cada nuevo elemento en el flujo, verifique si el nuevo elemento es más pequeño que el k-ésimo elemento más grande actual. Si es así, entonces ignóralo. Si no, elimine el elemento más pequeño de la array e inserte un nuevo elemento en orden. La complejidad temporal del procesamiento de un nuevo elemento es O(k).
Una mejor solución es utilizar un árbol de búsqueda binario autoequilibrado de tamaño k. El k’ésimo elemento más grande se puede encontrar en el tiempo O(Logk).
¿Cómo procesar un nuevo elemento de flujo?
Para cada nuevo elemento en el flujo, verifique si el nuevo elemento es más pequeño que el k-ésimo elemento más grande actual. Si es así, entonces ignóralo. Si no, elimine el elemento más pequeño del árbol e inserte un nuevo elemento. La complejidad temporal del procesamiento de un nuevo elemento es O(Logk).
Una solución eficiente es usar Min Heap de tamaño k para almacenar k elementos más grandes de flujo. El k-ésimo elemento más grande siempre está en la raíz y se puede encontrar en el tiempo O(1).
¿Cómo procesar un nuevo elemento de flujo?
Compare el nuevo elemento con la raíz del montón. Si el nuevo elemento es más pequeño, ignórelo. De lo contrario, reemplace la raíz con el nuevo elemento y llame a heapify para la raíz del montón modificado. La complejidad temporal de encontrar el k’ésimo elemento más grande es 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
Producción:
K is 3 Enter next element of stream 23 Enter next element of stream 10 Enter next element of stream 15 K'th largest element is 10 Enter next element of stream 70 K'th largest element is 15 Enter next element of stream 5 K'th largest element is 15 Enter next element of stream 80 K'th largest element is 23 Enter next element of stream 100 K'th largest element is 70 Enter next element of stream CTRL + C pressed
Implementación usando Priority Queue:
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
Python3
# Python program for the above approach from queue import PriorityQueue def kthLargest(k, arr, n): ans = [0]*n # Creating a min-heap using priority queue pq = PriorityQueue() # Iterating through each element for i in range(n): # If size of priority # queue is less than k if (pq.qsize() < k): pq.put(arr[i]) else: if (arr[i] > pq.queue[0]): pq.get() pq.put(arr[i]) # If size is less than k if (pq.qsize() < k): ans[i] = -1 else: ans[i] = pq.queue[0] return ans # Driver Code n = 6 arr = [1, 2, 3, 4, 5, 6] k = 4 # Function call v = kthLargest(k, arr, n) print(*v) # This code is contributed by Lovely Jain
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
Complejidad de Tiempo: O(nlogn)
Espacio Auxiliar: O(n), ya que se ha tomado n espacio extra.
Este artículo es una contribución de Shivam Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA