Encuentre la mediana de la array formada a partir de frecuencias dadas de elementos

Dada una array A[] que contiene N elementos de una array y su frecuencia en esa array (digamos arr[]), la tarea es encontrar la mediana de la array cuyos elementos y frecuencia se dan.

Nota: la mediana de una array es el elemento en el medio de la array ordenada

Ejemplos:

Entrada: A[] = { {1, 2}, {4, 2}, {5, 1} }
Salida: 4 
Explicación: La array cuyos elementos se dan es {1, 1, 4, 4, 5}. 
Por lo tanto, la mediana de la array será 4.

Entrada: A[] = { {3, 4}, {2, 3}, {9, 2} }
Salida: 3
Explicación : la array recién creada será {2, 2, 2, 3, 3, 3, 3 , 9, 9}. 
Por lo tanto, la mediana de la array será 3.

Enfoque ingenuo: el enfoque básico es crear la array y luego ordenar la array y encontrar el elemento medio de esa array.

Complejidad temporal: O(M * log M) donde M es la suma de las frecuencias de todos los elementos dados en A[].
Espacio Auxiliar: O(M)

Enfoque eficiente: como la suma de las frecuencias de los elementos presentes en A[] puede ser muy grande, no es factible construir una array. Esto se puede resolver de manera eficiente en base a la siguiente idea: 

Ordene la array A[] según el valor de los elementos. Ahora calcule el número total de elementos que estarán en la array formada a partir de estos elementos (digamos M ). El elemento en la posición M/2 es la mediana.
Así que itera desde los elementos mínimos y con la ayuda de sus frecuencias encuentra el elemento y la posición M/2th .

Siga los pasos a continuación para implementar la idea anterior:

• Inserte todos los elementos en un mapa con los elementos como clave y su frecuencia como valor (un mapa se ordena en función del valor de la clave. Por lo tanto, satisface la necesidad de clasificación).
• Cuente los elementos totales que estarán en la array. 
• Iterar desde los elementos mínimos y comprobar si el total de elementos hasta el valor actual es el mismo que M/2 :
  • Si es igual, entonces el elemento actual es la mediana requerida.
  • De lo contrario, aumente el número total de elementos hasta ahora.
• Devolver la mediana.

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Find median of the newly created array
int findMedian(vector<vector<int> > a, int n)
{
    map<int, int> m;
 
    // Size of the newly created array
    int totalsize = 0;
 
    // Put all elements in the map
    for (int i = 0; i < n; i++) {
        int val = a[i][0];
        int time = a[i][1];
        m[val] += time;
        totalsize += time;
    }
 
    // Find the element present at the middle
    // of the newly created array
    int meidanpos = totalsize / 2;
    long long pos = 0;
    for (auto it : m) {
 
        // If the pos + current element times
        // is greater than medianpos
        // then return current element
        if (pos + it.second > meidanpos) {
            return it.first;
        }
        else {
            pos += it.second;
        }
    }
}
 
// Driver Code
int main()
{
    vector<vector<int> > A;
    A = { { 1, 2 }, { 4, 2 }, { 5, 1 } };
    int N = A.size();
 
    // Function call
    cout << findMedian(A, N);
    return 0;
}

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // Find median of the newly created array
  public static int findMedian(int a[][], int n)
  {
    TreeMap<Integer, Integer> m
      = new TreeMap<Integer, Integer>();
 
    // Size of the newly created array
    int totalsize = 0;
 
    // Put all elements in the map
    for (int i = 0; i < n; i++) {
      int val = a[i][0];
      int time = a[i][1];
      if (m.get(val) != null)
        m.put(val, m.get(val) + time);
      else
        m.put(val, time);
      totalsize += time;
    }
 
    // Find the element present at the middle
    // of the newly created array
    int meidanpos = totalsize / 2;
    long pos = 0;
    for (Map.Entry<Integer, Integer> it :
         m.entrySet()) {
 
      // If the pos + current element times
      // is greater than medianpos
      // then return current element
      if (pos + it.getValue() > meidanpos) {
        return it.getKey();
      }
      else {
        pos += it.getValue();
      }
    }
    return 0;
  }
 
  public static void main(String[] args)
  {
 
    int A[][] = { { 1, 2 }, { 4, 2 }, { 5, 1 } };
    int N = A.length;
 
    // Function call
    System.out.print(findMedian(A, N));
  }
}
 
// This code is contributed by Rohit Pradhan

# Python3 code to implement the approach
 
# Find median of the newly created array
def findMedian(a, n):
    m = dict()
     
    # Size of the newly created array
    totalsize = 0
     
    # Put all elements in the map
    for i in range(n):
        val = a[i][0]
        time = a[i][1]
        if val in m:
            m[val] += time
        else:
            m[val] = time
        totalsize += time
     
    # find the element present at the middle
    # of the newly created array
    medianpos = totalsize // 2
    pos = 0
     
    for it in m.items():
        # if the pos + current element times
        # is greater than medianpos
        # then return the current element
        if pos + it[1] > medianpos:
            return it[0]
        else:
            pos += it[1]
 
# Driver Code
A = [[1, 2], [4, 2], [5, 1]]
N = len(A)
 
# Function Call
print(findMedian(A, N))
               
# This code is contributed by phasing17

// C# program to implement the approach
using System;
using System.Collections.Generic;
 
class GFG
{
   // Find median of the newly created array
  static int findMedian(int[,] a, int n)
  {
     
     Dictionary<int,int> m = new Dictionary<int,int>();
  
    // Size of the newly created array
    int totalsize = 0;
  
    // Put all elements in the map
    for (int i = 0; i < n; i++) {
      int val = a[i,0];
      int time = a[i,1];
      if (m.ContainsKey(val))
        m[val]=m[val] + time;
      else
        m[val]=time;
      totalsize += time;
    }
  
    // Find the element present at the middle
    // of the newly created array
    int meidanpos = totalsize / 2;
    long pos = 0;
    foreach(KeyValuePair<int, int> it in m)
    {
      // If the pos + current element times
      // is greater than medianpos
      // then return current element
      if (pos + it.Value > meidanpos) {
        return it.Key;
      }
      else {
        pos += it.Value;
      }
    }
    return 0;
  }
 
// Driver Code
public static void Main()
{
    int[,] A = { { 1, 2 }, { 4, 2 }, { 5, 1 } };
    int N = A.GetLength(0);;
  
    // Function call
    Console.Write(findMedian(A, N));
}
}
 
// This code is contributed by Pushpesh Raj

<script>
 
// JavaScript code to implement the approach
 
// Find median of the newly created array
function findMedian(a, n){
    let m = new Map()
     
    // Size of the newly created array
    let totalsize = 0
     
    // Put all elements in the map
    for(let i = 0; i < n; i++){
                 
        let val = a[i][0]
        let time = a[i][1]
        if(m.has(val))
            m.set(val,m.get(val)+time)
        else
            m.set(val,time)
        totalsize += time
    }
     
    // find the element present at the middle
    // of the newly created array
    let medianpos = Math.floor(totalsize / 2)
    let pos = 0
     
    for(let [it,it2] of m)
    {
     
        // if the pos + current element times
        // is greater than medianpos
        // then return the current element
        if(pos + it2 > medianpos)
            return it
        else
            pos += it2
    }
}
 
// Driver Code
let A = [[1, 2], [4, 2], [5, 1]]
let N = A.length
 
// Function Call
document.write(findMedian(A, N))
               
// This code is contributed by shinjanpatra
 
</script>

4

Complejidad temporal:  O(N * logN)
Espacio auxiliar:  O(N)