Dado que los enteros se leen de un flujo de datos. Encuentre la mediana de los elementos leídos de manera eficiente. Por simplicidad, suponga que no hay duplicados. Por ejemplo, consideremos la corriente 5, 15, 1, 3…
After reading 1st element of stream - 5 -> median - 5 After reading 2nd element of stream - 5, 15 -> median - 10 After reading 3rd element of stream - 5, 15, 1 -> median - 5 After reading 4th element of stream - 5, 15, 1, 3 -> median - 4, so on...
Para dejarlo claro, cuando el tamaño de entrada es impar, tomamos el elemento medio de los datos ordenados. Si el tamaño de entrada es par, seleccionamos el promedio de los dos elementos del medio en el flujo ordenado.
Tenga en cuenta que la salida es la mediana efectiva de los enteros leídos del flujo hasta el momento. Tal algoritmo se llama algoritmo en línea. Cualquier algoritmo que pueda garantizar la salida de i -elementos después de procesar i -ésimo elemento, se dice que es un algoritmo en línea . Analicemos tres soluciones al problema anterior.
Método 1: ordenación por inserción
Si podemos ordenar los datos tal como aparecen, podemos ubicar fácilmente el elemento mediano. Insertion Sort es uno de esos algoritmos en línea que ordena los datos aparecidos hasta ahora. En cualquier instancia de clasificación, por ejemplo, después de clasificar el i -ésimo elemento, se clasifican los primeros i elementos de la array. La ordenación por inserción no depende de datos futuros para ordenar la entrada de datos hasta ese punto. En otras palabras, la ordenación por inserción considera los datos ordenados hasta el momento al insertar el siguiente elemento. Esta es la parte clave del ordenamiento por inserción que lo convierte en un algoritmo en línea.
Sin embargo, la ordenación por inserción toma O(n 2 ) tiempo para ordenar n elementos. Tal vez podamos usar la búsqueda binaria en la ordenación por inserción para encontrar la ubicación del siguiente elemento en el tiempo O (log n). Sin embargo, no podemos hacer el movimiento de datos en el tiempo O (log n). No importa qué tan eficiente sea la implementación, toma tiempo polinomial en caso de ordenación por inserción.
Los lectores interesados pueden probar la implementación del Método 1.
C++
// This code is contributed by Anjali Saxena
#include <bits/stdc++.h>
using namespace std;
// Function to find position to insert current element of
// stream using binary search
int binarySearch(int arr[], int item, int low, int high)
{
if (low >= high) {
return (item > arr[low]) ? (low + 1) : low;
}
int mid = (low + high) / 2;
if (item == arr[mid])
return mid + 1;
if (item > arr[mid])
return binarySearch(arr, item, mid + 1, high);
return binarySearch(arr, item, low, mid - 1);
}
// Function to print median of stream of integers
void printMedian(int arr[], int n)
{
int i, j, pos, num;
int count = 1;
cout << "Median after reading 1"
<< " element is " << arr[0] << "\n";
for (i = 1; i < n; i++) {
float median;
j = i - 1;
num = arr[i];
// find position to insert current element in sorted
// part of array
pos = binarySearch(arr, num, 0, j);
// move elements to right to create space to insert
// the current element
while (j >= pos) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = num;
// increment count of sorted elements in array
count++;
// if odd number of integers are read from stream
// then middle element in sorted order is median
// else average of middle elements is median
if (count % 2 != 0) {
median = arr[count / 2];
}
else {
median = (arr[(count / 2) - 1] + arr[count / 2])
/ 2;
}
cout << "Median after reading " << i + 1
<< " elements is " << median << "\n";
}
}
// Driver Code
int main()
{
int arr[] = { 5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
printMedian(arr, n);
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG {
// Function to find position to insert current element of
// stream using binary search
static int binarySearch(int arr[], int item, int low, int high)
{
if (low >= high) {
return (item > arr[low]) ? (low + 1) : low;
}
int mid = (low + high) / 2;
if (item == arr[mid])
return mid + 1;
if (item > arr[mid])
return binarySearch(arr, item, mid + 1, high);
return binarySearch(arr, item, low, mid - 1);
}
// Function to print median of stream of integers
static void printMedian(int arr[], int n)
{
int i, j, pos, num;
int count = 1;
System.out.println( "Median after reading 1"
+ " element is " + arr[0]);
for (i = 1; i < n; i++) {
float median;
j = i - 1;
num = arr[i];
// find position to insert current element in sorted
// part of array
pos = binarySearch(arr, num, 0, j);
// move elements to right to create space to insert
// the current element
while (j >= pos) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = num;
// increment count of sorted elements in array
count++;
// if odd number of integers are read from stream
// then middle element in sorted order is median
// else average of middle elements is median
if (count % 2 != 0) {
median = arr[count / 2];
}
else {
median = (arr[(count / 2) - 1] + arr[count / 2])
/ 2;
}
System.out.println( "Median after reading " + (i + 1)
+ " elements is " + (int)median );
}
}
// Driver code
public static void main (String[] args) {
int arr[] = { 5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4 };
int n = arr.length;
printMedian(arr, n);
}
}
// This code is contributed by sanjoy_62.
Python3
# Function to find position to insert current element of
# stream using binary search
def binarySearch(arr, item, low, high):
if (low >= high):
return (low + 1) if (item > arr[low]) else low
mid = (low + high) // 2
if (item == arr[mid]):
return mid + 1
if (item > arr[mid]):
return binarySearch(arr, item, mid + 1, high)
return binarySearch(arr, item, low, mid - 1)
# Function to print median of stream of integers
def printMedian(arr, n):
i, j, pos, num = 0, 0, 0, 0
count = 1
print(f"Median after reading 1 element is {arr[0]}")
for i in range(1, n):
median = 0
j = i - 1
num = arr[i]
# find position to insert current element in sorted
# part of array
pos = binarySearch(arr, num, 0, j)
# move elements to right to create space to insert
# the current element
while (j >= pos):
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = num
# increment count of sorted elements in array
count += 1
# if odd number of integers are read from stream
# then middle element in sorted order is median
# else average of middle elements is median
if (count % 2 != 0):
median = arr[count // 2]
else:
median = (arr[(count // 2) - 1] + arr[count // 2]) // 2
print(f"Median after reading {i + 1} elements is {median} ")
# Driver Code
if __name__ == "__main__":
arr = [5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4]
n = len(arr)
printMedian(arr, n)
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG{
// Function to find position to insert current element of
// stream using binary search
static int binarySearch(int[] arr, int item, int low, int high)
{
if (low >= high) {
return (item > arr[low]) ? (low + 1) : low;
}
int mid = (low + high) / 2;
if (item == arr[mid])
return mid + 1;
if (item > arr[mid])
return binarySearch(arr, item, mid + 1, high);
return binarySearch(arr, item, low, mid - 1);
}
// Function to print median of stream of integers
static void printMedian(int[] arr, int n)
{
int i, j, pos, num;
int count = 1;
Console.WriteLine( "Median after reading 1"
+ " element is " + arr[0]);
for (i = 1; i < n; i++) {
float median;
j = i - 1;
num = arr[i];
// find position to insert current element in sorted
// part of array
pos = binarySearch(arr, num, 0, j);
// move elements to right to create space to insert
// the current element
while (j >= pos) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = num;
// increment count of sorted elements in array
count++;
// if odd number of integers are read from stream
// then middle element in sorted order is median
// else average of middle elements is median
if (count % 2 != 0) {
median = arr[count / 2];
}
else {
median = (arr[(count / 2) - 1] + arr[count / 2])
/ 2;
}
Console.WriteLine( "Median after reading " + (i + 1)
+ " elements is " + (int)median );
}
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4 };
int n = arr.Length;
printMedian(arr, n);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript implementation for the above approach
// Function to find position to insert current element of
// stream using binary search
const binarySearch = (arr, item, low, high) => {
if (low >= high) {
return (item > arr[low]) ? (low + 1) : low;
}
let mid = parseInt((low + high) / 2);
if (item == arr[mid])
return mid + 1;
if (item > arr[mid])
return binarySearch(arr, item, mid + 1, high);
return binarySearch(arr, item, low, mid - 1);
}
// Function to print median of stream of integers
const printMedian = (arr, n) => {
let i, j, pos, num;
let count = 1;
document.write(`Median after reading 1 element is ${arr[0]}<br/>`);
for (i = 1; i < n; i++) {
let median;
j = i - 1;
num = arr[i];
// find position to insert current element in sorted
// part of array
pos = binarySearch(arr, num, 0, j);
// move elements to right to create space to insert
// the current element
while (j >= pos) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = num;
// increment count of sorted elements in array
count++;
// if odd number of integers are read from stream
// then middle element in sorted order is median
// else average of middle elements is median
if (count % 2 != 0) {
median = arr[parseInt(count / 2)];
}
else {
median = parseInt((arr[parseInt(count / 2) - 1] + arr[parseInt(count / 2)]) / 2);
}
document.write(`Median after reading ${i + 1} elements is ${median}<br/>`);
}
}
// Driver Code
let arr = [5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4];
let n = arr.length;
printMedian(arr, n);
// This code is contributed by rakeshsahni
</script>
Median after reading 1 element is 5 Median after reading 2 elements is 10 Median after reading 3 elements is 5 Median after reading 4 elements is 4 Median after reading 5 elements is 3 Median after reading 6 elements is 4 Median after reading 7 elements is 5 Median after reading 8 elements is 6 Median after reading 9 elements is 7 Median after reading 10 elements is 6 Median after reading 11 elements is 7 Median after reading 12 elements is 6
Complejidad de Tiempo: O(n 2 )
Complejidad de Espacio: O(1)
Método 2: árbol de búsqueda binario autoequilibrado aumentado (AVL, RB, etc.)
En cada Node de BST, mantenga una cantidad de elementos en el subárbol con raíz en ese Node. Podemos usar un Node como la raíz de un árbol binario simple, cuyo hijo izquierdo es BST autoequilibrado con elementos menores que root y cuyo hijo derecho es BST autoequilibrado con elementos mayores que root. El elemento raíz siempre tiene una mediana efectiva .
Si los subárboles izquierdo y derecho contienen el mismo número de elementos, el Node raíz contiene el promedio de los datos raíz del subárbol izquierdo y derecho. De lo contrario, la raíz contiene los mismos datos que la raíz del subárbol que tiene más elementos. Después de procesar un elemento entrante, los subárboles izquierdo y derecho (BST) difieren al máximo en 1.
El BST autoequilibrado es costoso en la gestión del factor de equilibrio del BST. Sin embargo, proporcionan datos ordenados que no necesitamos. Solo necesitamos la mediana. El siguiente método utiliza Heaps para rastrear la mediana.
Método 3: montones De manera
similar al equilibrio de BST en el método 2 anterior, podemos usar un montón máximo en el lado izquierdo para representar elementos que son menos que efectivos mediana y un montón mínimo en el lado derecho para representar elementos que son mayores que efectivos mediana _
Después de procesar un elemento entrante, la cantidad de elementos en los montones difiere como máximo en 1 elemento. Cuando ambos montones contienen la misma cantidad de elementos, seleccionamos el promedio de los datos raíz de los montones como mediana efectiva . Cuando los montones no están equilibrados, seleccionamos la mediana efectiva de la raíz del montón que contiene más elementos.
A continuación se muestra la implementación del método anterior. Para que el algoritmo construya estos montones, lea el código resaltado.
C
#include <iostream>
using namespace std;
// Heap capacity
#define MAX_HEAP_SIZE (128)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
//// Utility functions
// exchange a and b
inline
void Exch(int &a, int &b)
{
int aux = a;
a = b;
b = aux;
}
// Greater and Smaller are used as comparators
bool Greater(int a, int b)
{
return a > b;
}
bool Smaller(int a, int b)
{
return a < b;
}
int Average(int a, int b)
{
return (a + b) / 2;
}
// Signum function
// = 0 if a == b - heaps are balanced
// = -1 if a < b - left contains less elements than right
// = 1 if a > b - left contains more elements than right
int Signum(int a, int b)
{
if( a == b )
return 0;
return a < b ? -1 : 1;
}
// Heap implementation
// The functionality is embedded into
// Heap abstract class to avoid code duplication
class Heap
{
public:
// Initializes heap array and comparator required
// in heapification
Heap(int *b, bool (*c)(int, int)) : A(b), comp(c)
{
heapSize = -1;
}
// Frees up dynamic memory
virtual ~Heap()
{
if( A )
{
delete[] A;
}
}
// We need only these four interfaces of Heap ADT
virtual bool Insert(int e) = 0;
virtual int GetTop() = 0;
virtual int ExtractTop() = 0;
virtual int GetCount() = 0;
protected:
// We are also using location 0 of array
int left(int i)
{
return 2 * i + 1;
}
int right(int i)
{
return 2 * (i + 1);
}
int parent(int i)
{
if( i <= 0 )
{
return -1;
}
return (i - 1)/2;
}
// Heap array
int *A;
// Comparator
bool (*comp)(int, int);
// Heap size
int heapSize;
// Returns top element of heap data structure
int top(void)
{
int max = -1;
if( heapSize >= 0 )
{
max = A[0];
}
return max;
}
// Returns number of elements in heap
int count()
{
return heapSize + 1;
}
// Heapification
// Note that, for the current median tracing problem
// we need to heapify only towards root, always
void heapify(int i)
{
int p = parent(i);
// comp - differentiate MaxHeap and MinHeap
// percolates up
if( p >= 0 && comp(A[i], A[p]) )
{
Exch(A[i], A[p]);
heapify(p);
}
}
// Deletes root of heap
int deleteTop()
{
int del = -1;
if( heapSize > -1)
{
del = A[0];
Exch(A[0], A[heapSize]);
heapSize--;
heapify(parent(heapSize+1));
}
return del;
}
// Helper to insert key into Heap
bool insertHelper(int key)
{
bool ret = false;
if( heapSize < MAX_HEAP_SIZE )
{
ret = true;
heapSize++;
A[heapSize] = key;
heapify(heapSize);
}
return ret;
}
};
// Specialization of Heap to define MaxHeap
class MaxHeap : public Heap
{
private:
public:
MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater) { }
~MaxHeap() { }
// Wrapper to return root of Max Heap
int GetTop()
{
return top();
}
// Wrapper to delete and return root of Max Heap
int ExtractTop()
{
return deleteTop();
}
// Wrapper to return # elements of Max Heap
int GetCount()
{
return count();
}
// Wrapper to insert into Max Heap
bool Insert(int key)
{
return insertHelper(key);
}
};
// Specialization of Heap to define MinHeap
class MinHeap : public Heap
{
private:
public:
MinHeap() : Heap(new int[MAX_HEAP_SIZE], &Smaller) { }
~MinHeap() { }
// Wrapper to return root of Min Heap
int GetTop()
{
return top();
}
// Wrapper to delete and return root of Min Heap
int ExtractTop()
{
return deleteTop();
}
// Wrapper to return # elements of Min Heap
int GetCount()
{
return count();
}
// Wrapper to insert into Min Heap
bool Insert(int key)
{
return insertHelper(key);
}
};
// Function implementing algorithm to find median so far.
int getMedian(int e, int &m, Heap &l, Heap &r)
{
// Are heaps balanced? If yes, sig will be 0
int sig = Signum(l.GetCount(), r.GetCount());
switch(sig)
{
case 1: // There are more elements in left (max) heap
if( e < m ) // current element fits in left (max) heap
{
// Remove top element from left heap and
// insert into right heap
r.Insert(l.ExtractTop());
// current element fits in left (max) heap
l.Insert(e);
}
else
{
// current element fits in right (min) heap
r.Insert(e);
}
// Both heaps are balanced
m = Average(l.GetTop(), r.GetTop());
break;
case 0: // The left and right heaps contain same number of elements
if( e < m ) // current element fits in left (max) heap
{
l.Insert(e);
m = l.GetTop();
}
else
{
// current element fits in right (min) heap
r.Insert(e);
m = r.GetTop();
}
break;
case -1: // There are more elements in right (min) heap
if( e < m ) // current element fits in left (max) heap
{
l.Insert(e);
}
else
{
// Remove top element from right heap and
// insert into left heap
l.Insert(r.ExtractTop());
// current element fits in right (min) heap
r.Insert(e);
}
// Both heaps are balanced
m = Average(l.GetTop(), r.GetTop());
break;
}
// No need to return, m already updated
return m;
}
void printMedian(int A[], int size)
{
int m = 0; // effective median
Heap *left = new MaxHeap();
Heap *right = new MinHeap();
for(int i = 0; i < size; i++)
{
m = getMedian(A[i], m, *left, *right);
cout << m << endl;
}
// C++ more flexible, ensure no leaks
delete left;
delete right;
}
// Driver code
int main()
{
int A[] = {5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4};
int size = ARRAY_SIZE(A);
// In lieu of A, we can also use data read from a stream
printMedian(A, size);
return 0;
}
Python3
# code from heapq import heappush, heappop, heapify import math minHeap=[] heapify(minHeap) maxHeap=[] heapify(maxHeap) def insertHeaps(num): heappush(maxHeap,-num) ### Pushing negative element to obtain a minHeap for heappush(minHeap,-heappop(maxHeap)) ### the negative counterpart if len(minHeap) > len(maxHeap): heappush(maxHeap,-heappop(minHeap)) def getMedian(): if len(minHeap)!= len(maxHeap): return -maxHeap[0] else: return (minHeap[0]- maxHeap[0])/2 if __name__== '__main__': A= [5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4] n= len(A) for i in range(n): insertHeaps(A[i]) print(math.floor(getMedian()))
Complejidad de tiempo: si omitimos la forma en que se leyó el flujo, la complejidad del hallazgo mediano es O (N log N) , ya que necesitamos leer el flujo y debido a las inserciones/eliminaciones de montón.
Espacio auxiliar: O(N)
A primera vista, el código anterior puede parecer complejo. Si lees el código cuidadosamente, es un algoritmo simple.
Mediana de flujo de enteros en ejecución usando STL
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