Dada una array de enteros arr[] y un entero k , la tarea es encontrar la mediana de cada ventana de tamaño k comenzando desde la izquierda y moviéndose hacia la derecha una posición cada vez.
Ejemplos:
Entrada: arr[] = {-1, 5, 13, 8, 2, 3, 3, 1}, k = 3
Salida: 5 8 8 3 3 3Entrada: arr[] = {-1, 5, 13, 8, 2, 3, 3, 1}, k = 4
Salida: 6,5 6,5 5,5 3,0 2,5
Enfoque: cree una clase de par para contener los elementos y su índice. También implementa la interfaz comparable para que Treeset invoque el método compareTo() para encontrar los Nodes. Tenga en cuenta que los dos pares son iguales solo cuando sus índices son iguales. Esto es importante ya que una ventana puede contener duplicados y podemos terminar eliminando varios elementos en una sola llamada remove() si solo verificamos el valor.
La idea es mantener dos conjuntos ordenados (minSet y maxSet) de objetos Pair de longitud (k/2) y (k/2) + 1 dependiendo de si k es par o impar, minSet siempre contendrá el primer conjunto de números ( menor) de la ventana k y maxSet contendrá el segundo conjunto de números (más grande).
A medida que movemos nuestra ventana, eliminaremos elementos de cualquiera de los conjuntos (log n) y agregaremos un nuevo elemento (log n) manteniendo la regla minSet y maxSet especificada anteriormente.
A continuación se muestra la implementación del enfoque anterior:
// Java implementation of the approach
import java.util.TreeSet;
public class GFG {
// Pair class for the value and its index
static class Pair implements Comparable<Pair> {
private int value, index;
// Constructor
public Pair(int v, int p)
{
value = v;
index = p;
}
// This method will be used by the treeset to
// search a value by index and setting the tree
// nodes (left or right)
@Override
public int compareTo(Pair o)
{
// Two nodes are equal only when
// their indices are same
if (index == o.index) {
return 0;
}
else if (value == o.value) {
return Integer.compare(index, o.index);
}
else {
return Integer.compare(value, o.value);
}
}
// Function to return the value
// of the current object
public int value()
{
return value;
}
// Update the value and the position
// for the same object to save space
public void renew(int v, int p)
{
value = v;
index = p;
}
@Override
public String toString()
{
return String.format("(%d, %d)", value, index);
}
}
// Function to print the median for the current window
static void printMedian(TreeSet<Pair> minSet,
TreeSet<Pair> maxSet, int window)
{
// If the window size is even then the
// median will be the average of the
// two middle elements
if (window % 2 == 0) {
System.out.print((minSet.last().value()
+ maxSet.first().value())
/ 2.0);
System.out.print(" ");
}
// Else it will be the middle element
else {
System.out.print(minSet.size() > maxSet.size()
? minSet.last().value()
: maxSet.first().value());
System.out.print(" ");
}
}
// Function to find the median
// of every window of size k
static void findMedian(int arr[], int k)
{
TreeSet<Pair> minSet = new TreeSet<>();
TreeSet<Pair> maxSet = new TreeSet<>();
// To hold the pairs, we will keep renewing
// these instead of creating the new pairs
Pair[] windowPairs = new Pair[k];
for (int i = 0; i < k; i++) {
windowPairs[i] = new Pair(arr[i], i);
}
// Add k/2 items to maxSet
for (int i = 0; i < k / 2; i++) {
maxSet.add(windowPairs[i]);
}
for (int i = k / 2; i < k; i++) {
// Below logic is to maintain the
// maxSet and the minSet criteria
if (arr[i] < maxSet.first().value()) {
minSet.add(windowPairs[i]);
}
else {
minSet.add(maxSet.pollFirst());
maxSet.add(windowPairs[i]);
}
}
printMedian(minSet, maxSet, k);
for (int i = k; i < arr.length; i++) {
// Get the pair at the start of the window, this
// will reset to 0 at every k, 2k, 3k, ...
Pair temp = windowPairs[i % k];
if (temp.value() <= minSet.last().value()) {
// Remove the starting pair of the window
minSet.remove(temp);
// Renew window start to new window end
temp.renew(arr[i], i);
// Below logic is to maintain the
// maxSet and the minSet criteria
if (temp.value() < maxSet.first().value()) {
minSet.add(temp);
}
else {
minSet.add(maxSet.pollFirst());
maxSet.add(temp);
}
}
else {
maxSet.remove(temp);
temp.renew(arr[i], i);
// Below logic is to maintain the
// maxSet and the minSet criteria
if (temp.value() > minSet.last().value()) {
maxSet.add(temp);
}
else {
maxSet.add(minSet.pollLast());
minSet.add(temp);
}
}
printMedian(minSet, maxSet, k);
}
}
// Driver code
public static void main(String[] args)
{
int[] arr = new int[] { 0, 9, 1, 8, 2,
7, 3, 6, 4, 5 };
int k = 3;
findMedian(arr, k);
}
}
1 8 2 7 3 6 4 5
Publicación traducida automáticamente
Artículo escrito por Rahul_Titare y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA