Dadas dos arrays arr[] de N enteros y W[] de N pesos donde W[i] es el peso del elemento arr[i] . La tarea es encontrar la mediana ponderada de la array dada.
Nota: La suma del peso de todos los elementos siempre será 1.
Deje que la array arr[] se organice en orden creciente con sus pesos correspondientes.
Si N es impar, entonces solo hay una mediana ponderada, digamos arr[k], que satisface la siguiente propiedad:
Si N es par, entonces hay dos medianas ponderadas, es decir, mediana ponderada superior e inferior.La mediana ponderada inferior para el elemento arr[k] que cumple lo siguiente:
La mediana ponderada superior para el elemento arr[k] que cumple lo siguiente:
Ejemplos:
Entrada: arr={5, 1, 3, 2, 4}, W=[0.25, 0.15, 0.2, 0.1, 0.3]
Salida: La mediana ponderada es el elemento 4
Explicación:
Aquí el número de elementos es impar, por lo que hay solo una mediana ponderada porque en K = 3 se cumple la condición anterior.
Los pesos acumulados a cada lado del elemento 4 son 0,45 y 0,25.Entrada: arr=[4, 1, 3, 2], W=[0.25, 0.49, 0.25, 0.01]
Salida:
La mediana ponderada inferior es el elemento 2
La mediana ponderada superior es el elemento 3
Explicación:
Aquí hay un número par de elementos, por lo que hay dos medianas ponderadas.
La mediana ponderada más baja está en K = 2 porque en K = 2 la condición anterior se cumple con un peso acumulativo en cada lado del elemento 2 de 0,49 y 0,5.
La mediana ponderada superior está en K = 3 porque en K = 3 la condición anterior se cumple con un peso acumulativo en cada lado del elemento 3 de 0,5 y 0,25.
Enfoque: siga los pasos a continuación para resolver el problema dado:
- Ahora, para encontrar la mediana de la array arr[] en orden creciente con su respectivo orden de peso, no se debe cambiar.
- Entonces, cree un conjunto de pares donde el primer elemento del par será arr[i] y el segundo elemento del par será su peso correspondiente W[i] .
- Luego ordene el conjunto de Pares de acuerdo con los valores de arr[] .
- Si el número de pares es impar, encuentre la mediana ponderada como:
- Recorra el conjunto de pares y calcule la suma agregando pesos.
- Cuando la suma sea superior a 0,5 , imprima el valor arr[i] de ese par.
- Pero, si el número de pares es par, encuentre las medianas ponderadas superior e inferior:
- Para la mediana inferior, recorra los pares establecidos desde la izquierda y calcule la suma agregando pesos.
- Cuando la suma sea mayor o igual a 0,5 , imprima el valor arr[i] de ese par.
- Para la mediana superior, recorra los pares de conjuntos desde la derecha y calcule la suma agregando pesos.
- Cuando la suma sea mayor o igual a 0,5 , imprima el valor arr[i] de ese par.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate weighted median
void weightedMedian(vector<int> arr,
vector<float> W)
{
// Store pr of arr[i] and W[i]
vector<pair<int, float>> pr;
for(int index = 0;
index < arr.size();
index++)
pr.push_back({arr[index],
W[index]});
// Sort the list of pr w.r.t.
// to their arr[] values
sort(pr.begin(), pr.end());
// If N is odd
if (arr.size() % 2 != 0)
{
// Traverse the set pr
// from left to right
float sums = 0;
for(auto element : pr)
{
// Update sums
sums += element.second;
// If sum becomes > 0.5
if (sums > 0.5)
cout << "The Weighted Median is element "
<< element.first << endl;
}
}
// If N is even
else
{
// For lower median traverse
// the set pr from left
float sums = 0;
for(auto element : pr)
{
// Update sums
sums += element.second;
// When sum >= 0.5
if (sums >= 0.5)
{
cout << "Lower Weighted Median is element "
<< element.first << endl;
break;
}
}
// For upper median traverse
// the set pr from right
sums = 0;
for(int index = pr.size() - 1;
index >= 0;
index--)
{
int element = pr[index].first;
float weight = pr[index].second;
// Update sums
sums += weight;
// When sum >= 0.5
if (sums >= 0.5)
{
cout << "Upper Weighted Median is element "
<< element;
break;
}
}
}
}
// Driver Code
int main()
{
// Given array arr[]
vector<int> arr = { 4, 1, 3, 2 };
// Given weights W[]
vector<float> W = { 0.25, 0.49, 0.25, 0.01 };
// Function Call
weightedMedian(arr, W);
}
// This code is contributed by mohit kumar 29
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
static class Pair implements Comparable<Pair>
{
int first;
double second;
Pair(int f, double s)
{
first = f;
second = s;
}
@Override
public int compareTo(Pair o)
{
if(this.second > o.second)
return 1;
else if(this.second == o.second)
return 0;
return -1;
}
}
// Function to calculate weighted median
static void weightedMedian(Vector<Integer> arr,
Vector<Double> W)
{
// Store pr of arr[i] and W[i]
Vector<Pair> pr = new Vector<>();
for(int index = 0;
index < arr.size();
index++)
pr.add(new Pair(arr.get(index),
W.get(index)));
// Sort the list of pr w.r.t.
// to their arr[] values
Collections.sort(pr);
// If N is odd
if (arr.size() % 2 != 0)
{
// Traverse the set pr
// from left to right
float sums = 0;
for(Pair element : pr)
{
// Update sums
sums += element.second;
// If sum becomes > 0.5
if (sums > 0.5)
System.out.print(
"The Weighted Median is element " +
element.first + "\n");
}
}
// If N is even
else
{
// For lower median traverse
// the set pr from left
double sums = 0;
for(Pair element : pr)
{
// Update sums
sums += element.second;
// When sum >= 0.5
if (sums <= 0.5)
{
System.out.print(
"Lower Weighted Median is element " +
element.first + "\n");
break;
}
}
// For upper median traverse
// the set pr from right
sums = 0;
for(int index = pr.size() - 1;
index >= 0; index--)
{
int element = pr.get(index).first;
double weight = pr.get(index).second;
// Update sums
sums += weight;
// When sum >= 0.5
if (sums >= 0.5)
{
System.out.print(
"Upper Weighted Median is element " +
element);
break;
}
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
Vector<Integer> arr = new Vector<>();
arr.add(4);
arr.add(1);
arr.add(3);
arr.add(2);
// Given weights W[]
Vector<Double> W = new Vector<>();
W.add(0.25);
W.add(0.49);
W.add(0.25);
W.add(0.01);
// Function Call
weightedMedian(arr, W);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach
# Function to calculate weighted median
def weightedMedian(arr, W):
# Store pairs of arr[i] and W[i]
pairs = []
for index in range(len(arr)):
pairs.append([arr[index], W[index]])
# Sort the list of pairs w.r.t.
# to their arr[] values
pairs.sort(key = lambda p: p[0])
# If N is odd
if len(arr) % 2 != 0:
# Traverse the set pairs
# from left to right
sums = 0
for element, weight in pairs:
# Update sums
sums += weight
# If sum becomes > 0.5
if sums > 0.5:
print("The Weighted Median", end = ' ')
print("is element {}".format(element))
# If N is even
else:
# For lower median traverse
# the set pairs from left
sums = 0
for element, weight in pairs:
# Update sums
sums += weight
# When sum >= 0.5
if sums >= 0.5:
print("Lower Weighted Median", end = ' ')
print("is element {}".format(element))
break
# For upper median traverse
# the set pairs from right
sums = 0
for index in range(len(pairs)-1, -1, -1):
element = pairs[index][0]
weight = pairs[index][1]
# Update sums
sums += weight
# When sum >= 0.5
if sums >= 0.5:
print("Upper Weighted Median", end = ' ')
print("is element {}".format(element))
break
# Driver Code
if __name__ == "__main__":
# Given array arr[]
arr = [4, 1, 3, 2]
# Given weights W[]
W = [0.25, 0.49, 0.25, 0.01]
# Function Call
weightedMedian(arr, W)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate weighted median
static void weightedMedian(int[] arr,
float[] W)
{
// Store pr of arr[i] and W[i]
List<Tuple<int,
float>> pr = new List<Tuple<int,
float>>();
for(int index = 0; index < arr.Length; index++)
pr.Add(new Tuple<int, float>(arr[index], W[index]));
// Sort the list of pr w.r.t.
// to their arr[] values
pr.Sort();
// If N is odd
if (arr.Length % 2 != 0)
{
// Traverse the set pr
// from left to right
float sums = 0;
foreach(Tuple<int, float> element in pr)
{
// Update sums
sums += element.Item2;
// If sum becomes > 0.5
if (sums > 0.5)
Console.WriteLine("The Weighted Median " +
"is element " + element.Item1);
}
}
// If N is even
else
{
// For lower median traverse
// the set pr from left
float sums = 0;
foreach(Tuple<int, float> element in pr)
{
// Update sums
sums += element.Item2;
// When sum >= 0.5
if (sums >= 0.5)
{
Console.WriteLine("Lower Weighted Median " +
"is element " + element.Item1);
break;
}
}
// For upper median traverse
// the set pr from right
sums = 0;
for(int index = pr.Count - 1; index >= 0; index--)
{
int element = pr[index].Item1;
float weight = pr[index].Item2;
// Update sums
sums += weight;
// When sum >= 0.5
if (sums >= 0.5)
{
Console.Write("Upper Weighted Median " +
"is element " + element);
break;
}
}
}
}
// Driver code
static void Main()
{
// Given array arr[]
int[] arr = { 4, 1, 3, 2 };
// Given weights W[]
float[] W = { 0.25f, 0.49f, 0.25f, 0.01f };
// Function Call
weightedMedian(arr, W);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the
// above approach
// Function to calculate weighted median
function weightedMedian(arr,W)
{
// Store pr of arr[i] and W[i]
let pr = [];
for(let index = 0;
index < arr.length;
index++)
pr.push([arr[index],
W[index]]);
// Sort the list of pr w.r.t.
// to their arr[] values
(pr).sort(function(a,b){return a[1]-b[1];});
// If N is odd
if (arr.length % 2 != 0)
{
// Traverse the set pr
// from left to right
let sums = 0;
for(let element=0;element< pr.length;element++)
{
// Update sums
sums += pr[element][1];
// If sum becomes > 0.5
if (sums > 0.5)
document.write(
"The Weighted Median is element " +
pr[element][0] + "<br>");
}
}
// If N is even
else
{
// For lower median traverse
// the set pr from left
let sums = 0;
for(let element=0;element< pr.length;element++)
{
// Update sums
sums += pr[element][1];
// When sum >= 0.5
if (sums <= 0.5)
{
document.write(
"Lower Weighted Median is element " +
pr[element][0] + "<br>");
break;
}
}
// For upper median traverse
// the set pr from right
sums = 0;
for(let index = pr.length - 1;
index >= 0; index--)
{
let element = pr[index][0];
let weight = pr[index][1];
// Update sums
sums += weight;
// When sum >= 0.5
if (sums >= 0.5)
{
document.write(
"Upper Weighted Median is element " +
element);
break;
}
}
}
}
// Driver Code
// Given array arr[]
let arr = [];
arr.push(4);
arr.push(1);
arr.push(3);
arr.push(2);
// Given weights W[]
let W = [];
W.push(0.25);
W.push(0.49);
W.push(0.25);
W.push(0.01);
// Function Call
weightedMedian(arr, W);
// This code is contributed by patel2127
</script>
Producción:
Lower Weighted Median is element 2 Upper Weighted Median is element 3
Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por BIRANCHINARAYANPADHI y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA