Dada una array sin ordenar arr[] de longitud N , la tarea es encontrar la mediana de esta array.
La mediana de una array ordenada de tamaño N se define como el elemento del medio cuando n es impar y el promedio de los dos elementos del medio cuando n es par.
Ejemplos:
Entrada: arr[] = {12, 3, 5, 7, 4, 19, 26}
Salida: 7
Secuencia ordenada de array dada arr[] = {3, 4, 5, 7, 12, 19, 26}
Dado que el número de elementos es impar, la mediana es el cuarto elemento en la secuencia ordenada de la array dada arr[], que es 7Entrada: arr[] = {12, 3, 5, 7, 4, 26}
Salida: 6
Dado que el número de elementos es par, la mediana es el promedio del tercer y cuarto elemento en la secuencia ordenada de la array dada arr[], lo que significa ( 5 + 7)/2 = 6
Enfoque ingenuo:
- Ordene la array arr[] en orden creciente.
- Si el número de elementos en arr[] es impar, entonces la mediana es arr[n/2] .
- Si el número de elementos en arr[] es par, la mediana es el promedio de arr[n/2] y arr[n/2+1] .
Consulte este artículo para la implementación del enfoque anterior.
Enfoque eficiente: uso de QuickSelect aleatorio
- Elija aleatoriamente el elemento pivote de arr[] y use el paso de partición del algoritmo de clasificación rápida para organizar todos los elementos más pequeños que el pivote a su izquierda y los elementos más grandes que él a su derecha.
- Si después del paso anterior, la posición del pivote elegido es el medio de la array, entonces es la mediana requerida de la array dada.
- Si la posición está antes del elemento central, repita el paso para el subarreglo a partir del índice inicial anterior y el pivote elegido como índice final.
- Si la posición está después del elemento central, repita el paso para el subarreglo comenzando desde el pivote elegido y terminando en el índice final anterior.
- Tenga en cuenta que en el caso de un número par de elementos, se deben encontrar los dos elementos centrales y su promedio será la mediana de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find median of
// an array
#include "bits/stdc++.h"
using namespace std;
// Utility function to swapping of element
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Returns the correct position of
// pivot element
int Partition(int arr[], int l, int r)
{
int lst = arr[r], i = l, j = l;
while (j < r) {
if (arr[j] < lst) {
swap(&arr[i], &arr[j]);
i++;
}
j++;
}
swap(&arr[i], &arr[r]);
return i;
}
// Picks a random pivot element between
// l and r and partitions arr[l..r]
// around the randomly picked element
// using partition()
int randomPartition(int arr[], int l,
int r)
{
int n = r - l + 1;
int pivot = rand() % n;
swap(&arr[l + pivot], &arr[r]);
return Partition(arr, l, r);
}
// Utility function to find median
void MedianUtil(int arr[], int l, int r,
int k, int& a, int& b)
{
// if l < r
if (l <= r) {
// Find the partition index
int partitionIndex
= randomPartition(arr, l, r);
// If partition index = k, then
// we found the median of odd
// number element in arr[]
if (partitionIndex == k) {
b = arr[partitionIndex];
if (a != -1)
return;
}
// If index = k - 1, then we get
// a & b as middle element of
// arr[]
else if (partitionIndex == k - 1) {
a = arr[partitionIndex];
if (b != -1)
return;
}
// If partitionIndex >= k then
// find the index in first half
// of the arr[]
if (partitionIndex >= k)
return MedianUtil(arr, l,
partitionIndex - 1,
k, a, b);
// If partitionIndex <= k then
// find the index in second half
// of the arr[]
else
return MedianUtil(arr,
partitionIndex + 1,
r, k, a, b);
}
return;
}
// Function to find Median
void findMedian(int arr[], int n)
{
int ans, a = -1, b = -1;
// If n is odd
if (n % 2 == 1) {
MedianUtil(arr, 0, n - 1,
n / 2, a, b);
ans = b;
}
// If n is even
else {
MedianUtil(arr, 0, n - 1,
n / 2, a, b);
ans = (a + b) / 2;
}
// Print the Median of arr[]
cout << "Median = " << ans;
}
// Driver program to test above methods
int main()
{
int arr[] = { 12, 3, 5, 7, 4, 19, 26 };
int n = sizeof(arr) / sizeof(arr[0]);
findMedian(arr, n);
return 0;
}
Java
// JAVA program to find median of
// an array
class GFG
{
static int a, b;
// Utility function to swapping of element
static int[] swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Returns the correct position of
// pivot element
static int Partition(int arr[], int l, int r)
{
int lst = arr[r], i = l, j = l;
while (j < r)
{
if (arr[j] < lst)
{
arr = swap(arr, i, j);
i++;
}
j++;
}
arr = swap(arr, i, r);
return i;
}
// Picks a random pivot element between
// l and r and partitions arr[l..r]
// around the randomly picked element
// using partition()
static int randomPartition(int arr[], int l, int r)
{
int n = r - l + 1;
int pivot = (int) (Math.random() % n);
arr = swap(arr, l + pivot, r);
return Partition(arr, l, r);
}
// Utility function to find median
static int MedianUtil(int arr[], int l, int r, int k)
{
// if l < r
if (l <= r)
{
// Find the partition index
int partitionIndex = randomPartition(arr, l, r);
// If partition index = k, then
// we found the median of odd
// number element in arr[]
if (partitionIndex == k)
{
b = arr[partitionIndex];
if (a != -1)
return Integer.MIN_VALUE;
}
// If index = k - 1, then we get
// a & b as middle element of
// arr[]
else if (partitionIndex == k - 1)
{
a = arr[partitionIndex];
if (b != -1)
return Integer.MIN_VALUE;
}
// If partitionIndex >= k then
// find the index in first half
// of the arr[]
if (partitionIndex >= k)
return MedianUtil(arr, l, partitionIndex - 1, k);
// If partitionIndex <= k then
// find the index in second half
// of the arr[]
else
return MedianUtil(arr, partitionIndex + 1, r, k);
}
return Integer.MIN_VALUE;
}
// Function to find Median
static void findMedian(int arr[], int n)
{
int ans;
a = -1;
b = -1;
// If n is odd
if (n % 2 == 1)
{
MedianUtil(arr, 0, n - 1, n / 2);
ans = b;
}
// If n is even
else
{
MedianUtil(arr, 0, n - 1, n / 2);
ans = (a + b) / 2;
}
// Print the Median of arr[]
System.out.print("Median = " + ans);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12, 3, 5, 7, 4, 19, 26 };
int n = arr.length;
findMedian(arr, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find median of
# an array
import random
a, b = None, None;
# Returns the correct position of
# pivot element
def Partition(arr, l, r) :
lst = arr[r]; i = l; j = l;
while (j < r) :
if (arr[j] < lst) :
arr[i], arr[j] = arr[j],arr[i];
i += 1;
j += 1;
arr[i], arr[r] = arr[r],arr[i];
return i;
# Picks a random pivot element between
# l and r and partitions arr[l..r]
# around the randomly picked element
# using partition()
def randomPartition(arr, l, r) :
n = r - l + 1;
pivot = random.randrange(1, 100) % n;
arr[l + pivot], arr[r] = arr[r], arr[l + pivot];
return Partition(arr, l, r);
# Utility function to find median
def MedianUtil(arr, l, r,
k, a1, b1) :
global a, b;
# if l < r
if (l <= r) :
# Find the partition index
partitionIndex = randomPartition(arr, l, r);
# If partition index = k, then
# we found the median of odd
# number element in arr[]
if (partitionIndex == k) :
b = arr[partitionIndex];
if (a1 != -1) :
return;
# If index = k - 1, then we get
# a & b as middle element of
# arr[]
elif (partitionIndex == k - 1) :
a = arr[partitionIndex];
if (b1 != -1) :
return;
# If partitionIndex >= k then
# find the index in first half
# of the arr[]
if (partitionIndex >= k) :
return MedianUtil(arr, l, partitionIndex - 1, k, a, b);
# If partitionIndex <= k then
# find the index in second half
# of the arr[]
else :
return MedianUtil(arr, partitionIndex + 1, r, k, a, b);
return;
# Function to find Median
def findMedian(arr, n) :
global a;
global b;
a = -1;
b = -1;
# If n is odd
if (n % 2 == 1) :
MedianUtil(arr, 0, n - 1, n // 2, a, b);
ans = b;
# If n is even
else :
MedianUtil(arr, 0, n - 1, n // 2, a, b);
ans = (a + b) // 2;
# Print the Median of arr[]
print("Median = " ,ans);
# Driver code
arr = [ 12, 3, 5, 7, 4, 19, 26 ];
n = len(arr);
findMedian(arr, n);
# This code is contributed by AnkitRai01
C#
// C# program to find median of
// an array
using System;
class GFG
{
static int a, b;
// Utility function to swapping of element
static int[] swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Returns the correct position of
// pivot element
static int Partition(int []arr, int l, int r)
{
int lst = arr[r], i = l, j = l;
while (j < r)
{
if (arr[j] < lst)
{
arr = swap(arr, i, j);
i++;
}
j++;
}
arr = swap(arr, i, r);
return i;
}
// Picks a random pivot element between
// l and r and partitions arr[l..r]
// around the randomly picked element
// using partition()
static int randomPartition(int []arr, int l, int r)
{
int n = r - l + 1;
int pivot = (int) (new Random().Next() % n);
arr = swap(arr, l + pivot, r);
return Partition(arr, l, r);
}
// Utility function to find median
static int MedianUtil(int []arr, int l, int r, int k)
{
// if l < r
if (l <= r)
{
// Find the partition index
int partitionIndex = randomPartition(arr, l, r);
// If partition index = k, then
// we found the median of odd
// number element in []arr
if (partitionIndex == k)
{
b = arr[partitionIndex];
if (a != -1)
return int.MinValue;
}
// If index = k - 1, then we get
// a & b as middle element of
// []arr
else if (partitionIndex == k - 1)
{
a = arr[partitionIndex];
if (b != -1)
return int.MinValue;
}
// If partitionIndex >= k then
// find the index in first half
// of the []arr
if (partitionIndex >= k)
return MedianUtil(arr, l, partitionIndex - 1, k);
// If partitionIndex <= k then
// find the index in second half
// of the []arr
else
return MedianUtil(arr, partitionIndex + 1, r, k);
}
return int.MinValue;
}
// Function to find Median
static void findMedian(int []arr, int n)
{
int ans;
a = -1;
b = -1;
// If n is odd
if (n % 2 == 1)
{
MedianUtil(arr, 0, n - 1, n / 2);
ans = b;
}
// If n is even
else
{
MedianUtil(arr, 0, n - 1, n / 2);
ans = (a + b) / 2;
}
// Print the Median of []arr
Console.Write("Median = " + ans);
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 12, 3, 5, 7, 4, 19, 26 };
int n = arr.Length;
findMedian(arr, n);
}
}
// This code is contributed by PrinciRaj1992
Producción:
Median = 7
Complejidad del tiempo:
- Análisis del mejor caso: O(1)
- Análisis de casos promedio: O(N)
- Análisis del peor de los casos: O(N 2 )
Espacio auxiliar: O(N)
¿Me pregunto cómo?
Referencia: ByStanfordUniversity
Publicación traducida automáticamente
Artículo escrito por Hrudwik_Dhulipalla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA