Dada una array arr[] de longitud N , la tarea es encontrar la mediana de las diferencias de todos los pares de elementos de la array.
Ejemplo:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 1
Explicación:
La diferencia de todos los pares de la array dada son {2 – 1, 3 – 2, 4 – 3, 3 – 1, 4 – 2 , 4 – 1} = {1, 1, 1, 2, 2, 3}.
Dado que la array contiene 6 elementos, la mediana es el elemento en el índice 3 de la array de diferencias.
Por lo tanto, la respuesta es 1.
Entrada: arr[] = {1, 3, 5}
Salida: 2
Explicación: La array de diferencias es {2, 2, 4}. Por lo tanto, la mediana es 2.
Enfoque ingenuo: la tarea es generar todos los pares posibles de la array dada y calcular la diferencia de cada par en la array arr[] y almacenarlos en la array diff[] . Ordene diff[] y encuentre el elemento del medio.
Complejidad de tiempo: O(N 2 *log(N 2 ))
Espacio auxiliar: O(N 2 )
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la búsqueda y clasificación binaria . Siga los pasos a continuación para resolver el problema:
- Ordenar la array dada.
- Inicialice low=0 y high=arr[N-1]-arr[0] .
- Calcula medio-igual a (bajo + alto) / 2 .
- Calcular el número de diferencias menores que mid . Si excede el índice mediano de la array de diferencias, [ceil(N * (N – 1) / 2)] , entonces actualice alto como mid – 1 . De lo contrario, actualice low as mid + 1 .
- Repita los pasos anteriores hasta que el alto y el bajo se igualen.
A continuación se muestra el enfoque de implementación anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function check if mid can be median
// index of the difference array
bool possible(ll mid, vector<ll>& a)
{
// Size of the array
ll n = a.size();
// Total possible no of pair
// possible
ll total = (n * (n - 1)) / 2;
// The index of the element in the
// difference of all pairs
// from the array
ll need = (total + 1) / 2;
ll count = 0;
ll start = 0, end = 1;
// Count the number of pairs
// having difference <= mid
while (end < n) {
if (a[end] - a[start] <= mid) {
end++;
}
else {
count += (end - start - 1);
start++;
}
}
// If the difference between end
// and first element is less then
// or equal to mid
if (end == n && start < end
&& a[end - 1] - a[start] <= mid) {
ll t = end - start - 1;
count += (t * (t + 1) / 2);
}
// Checking for the no of element less than
// or equal to mid is greater than median or
// not
if (count >= need)
return true;
else
return false;
}
// Function to calculate the median
// of differences of all pairs
// from the array
ll findMedian(vector<ll>& a)
{
// Size of the array
ll n = a.size();
// Initialising the low and high
ll low = 0, high = a[n - 1] - a[0];
// Binary search
while (low <= high) {
// Calculate mid
ll mid = (low + high) / 2;
// If mid can be the median
// of the array
if (possible(mid, a))
high = mid - 1;
else
low = mid + 1;
}
// Returning the median of the
// differences of pairs from
// the array
return high + 1;
}
// Driver Code
int main()
{
vector<ll> a = { 1, 7, 5, 2 };
sort(a.begin(), a.end());
cout << findMedian(a) << endl;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function check if mid can be median
// index of the difference array
static boolean possible(long mid, int[] a)
{
// Size of the array
long n = a.length;
// Total possible no of pair
// possible
long total = (n * (n - 1)) / 2;
// The index of the element in the
// difference of all pairs
// from the array
long need = (total + 1) / 2;
long count = 0;
long start = 0, end = 1;
// Count the number of pairs
// having difference <= mid
while (end < n)
{
if (a[(int)end] - a[(int)start] <= mid)
{
end++;
}
else
{
count += (end - start - 1);
start++;
}
}
// If the difference between end
// and first element is less then
// or equal to mid
if (end == n && start < end &&
a[(int)end - 1] - a[(int)start] <= mid)
{
long t = end - start - 1;
count += (t * (t + 1) / 2);
}
// Checking for the no of element less than
// or equal to mid is greater than median or
// not
if (count >= need)
return true;
else
return false;
}
// Function to calculate the median
// of differences of all pairs
// from the array
static long findMedian(int[] a)
{
// Size of the array
long n = a.length;
// Initialising the low and high
long low = 0, high = a[(int)n - 1] - a[0];
// Binary search
while (low <= high)
{
// Calculate mid
long mid = (low + high) / 2;
// If mid can be the median
// of the array
if (possible(mid, a))
high = mid - 1;
else
low = mid + 1;
}
// Returning the median of the
// differences of pairs from
// the array
return high + 1;
}
// Driver code
public static void main (String[] args)
{
int[] a = { 1, 7, 5, 2 };
Arrays.sort(a);
System.out.println(findMedian(a));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # Function check if mid can be median # index of the difference array def possible(mid, a): # Size of the array n = len(a); # Total possible no of pair # possible total = (n * (n - 1)) // 2; # The index of the element in the # difference of all pairs # from the array need = (total + 1) // 2; count = 0; start = 0; end = 1; # Count the number of pairs # having difference <= mid while (end < n): if (a[end] - a[start] <= mid): end += 1; else: count += (end - start - 1); start += 1; # If the difference between end # and first element is less then # or equal to mid if (end == n and start < end and a[end - 1] - a[start] <= mid): t = end - start - 1; count += (t * (t + 1) // 2); # Checking for the no of element # less than or equal to mid is # greater than median or not if (count >= need): return True; else: return False; # Function to calculate the median # of differences of all pairs # from the array def findMedian(a): # Size of the array n = len(a); # Initialising the low and high low = 0; high = a[n - 1] - a[0]; # Binary search while (low <= high): # Calculate mid mid = (low + high) // 2; # If mid can be the median # of the array if (possible(mid, a)): high = mid - 1; else : low = mid + 1; # Returning the median of the # differences of pairs from # the array return high + 1; # Driver Code if __name__ == "__main__" : a = [ 1, 7, 5, 2 ]; a.sort() print(findMedian(a)); # This code is contributed by AnkitRai01
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function check if mid can be median
// index of the difference array
static bool possible(long mid, int[] a)
{
// Size of the array
long n = a.Length;
// Total possible no of pair
// possible
long total = (n * (n - 1)) / 2;
// The index of the element in the
// difference of all pairs
// from the array
long need = (total + 1) / 2;
long count = 0;
long start = 0, end = 1;
// Count the number of pairs
// having difference <= mid
while (end < n)
{
if (a[(int)end] - a[(int)start] <= mid)
{
end++;
}
else
{
count += (end - start - 1);
start++;
}
}
// If the difference between end
// and first element is less then
// or equal to mid
if (end == n && start < end &&
a[(int)end - 1] - a[(int)start] <= mid)
{
long t = end - start - 1;
count += (t * (t + 1) / 2);
}
// Checking for the no of element less than
// or equal to mid is greater than median or
// not
if (count >= need)
return true;
else
return false;
}
// Function to calculate the median
// of differences of all pairs
// from the array
static long findMedian(int[] a)
{
// Size of the array
long n = a.Length;
// Initialising the low and high
long low = 0, high = a[(int)n - 1] - a[0];
// Binary search
while (low <= high)
{
// Calculate mid
long mid = (low + high) / 2;
// If mid can be the median
// of the array
if (possible(mid, a))
high = mid - 1;
else
low = mid + 1;
}
// Returning the median of the
// differences of pairs from
// the array
return high + 1;
}
// Driver code
public static void Main (string[] args)
{
int[] a = { 1, 7, 5, 2 };
Array.Sort(a);
Console.Write(findMedian(a));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function check if mid can be median
// index of the difference array
function possible(mid, a)
{
// Size of the array
let n = a.length;
// Total possible no of pair
// possible
let total = parseInt((n * (n - 1)) / 2);
// The index of the element in the
// difference of all pairs
// from the array
let need = parseInt((total + 1) / 2);
let count = 0;
let start = 0, end = 1;
// Count the number of pairs
// having difference <= mid
while (end < n) {
if (a[end] - a[start] <= mid) {
end++;
}
else {
count += (end - start - 1);
start++;
}
}
// If the difference between end
// and first element is less then
// or equal to mid
if (end == n && start < end
&& a[end - 1] - a[start] <= mid) {
let t = end - start - 1;
count += parseInt(t * (t + 1) / 2);
}
// Checking for the no of element less than
// or equal to mid is greater than median or
// not
if (count >= need)
return true;
else
return false;
}
// Function to calculate the median
// of differences of all pairs
// from the array
function findMedian(a)
{
// Size of the array
let n = a.length;
// Initialising the low and high
let low = 0, high = a[n - 1] - a[0];
// Binary search
while (low <= high) {
// Calculate mid
let mid = (low + high) / 2;
// If mid can be the median
// of the array
if (possible(mid, a))
high = mid - 1;
else
low = mid + 1;
}
// Returning the median of the
// differences of pairs from
// the array
return high + 1;
}
// Driver Code
let a = [ 1, 7, 5, 2 ];
a.sort();
document.write(findMedian(a));
</script>
Producción:
3
Complejidad temporal: O(N*log(M)), donde N es el número de elementos y M es la diferencia máxima entre pares de elementos de un arreglo.
Espacio Auxiliar: O(1)