Esta es una extensión de la mediana de dos arreglos ordenados de igual tamaño. Aquí también manejamos arrays de tamaño desigual.
Ejemplos:
Input: a[] = {1, 12, 15, 26, 38}
b[] = {2, 13, 24}
Output: 14
Explanation:
After merging arrays the result is
1, 2, 12, 13, 15, 24, 26, 38
median = (13 + 15)/2 = 14.
Input: a[] = {1, 3, 5, 7}
b[] = {2, 4, 6, 8}
Output: 5
Explanation :
After merging arrays the result is
1, 2, 3, 4, 5, 6, 7, 8, 9
median = 5
Acercarse:
- El enfoque discutido en esta publicación es similar al método 1 de mediana de igual tamaño . Utilice el procedimiento de fusión de tipo de fusión .
- Mantenga una variable para rastrear el conteo mientras compara elementos de dos arrays.
- Realiza la fusión de dos arrays ordenadas. Aumente el valor de recuento a medida que se inserte un nuevo elemento.
- La forma más eficiente de fusionar dos arrays es comparar la parte superior de ambas arrays y sacar el valor más pequeño y aumentar el conteo.
- Continúe comparando los elementos superiores/primeros de ambas arrays hasta que no queden elementos en ninguna array.
- Ahora, para encontrar la mediana, hay que manejar dos casos.
- Si la suma de la longitud de los tamaños de la array es par, almacene los elementos cuando el recuento tenga un valor ((n1 + n2)/2)-1 y (n1 + n2)/2 en la array combinada, agregue los elementos y divida por 2 devuelve el valor como mediana.
- Si el valor (la suma de los tamaños) es impar, devuelva el elemento (n1 + n2)/2 (cuando el valor de la cuenta es (n1 + n2)/2) como mediana.
C++
// A C++ program to find median of two sorted arrays of
// unequal sizes
#include <bits/stdc++.h>
using namespace std;
// A utility function to find median of two integers
/* This function returns median of a[] and b[].
Assumptions in this function: Both a[] and b[]
are sorted arrays */
float findmedian(int a[], int n1, int b[], int n2)
{
int i = 0; /* Current index of
i/p array a[] */
int j = 0; /* Current index of
i/p array b[] */
int k;
int m1 = -1, m2 = -1;
for (k = 0; k <= (n1 + n2) / 2; k++) {
if (i < n1 && j < n2) {
if (a[i] < b[j]) {
m2 = m1;
m1 = a[i];
i++;
}
else {
m2 = m1;
m1 = b[j];
j++;
}
}
/* Below is to handle the case where
all elements of a[] are
smaller than smallest(or first)
element of b[] or a[] is empty*/
else if (i == n1) {
m2 = m1;
m1 = b[j];
j++;
}
/* Below is to handle case where
all elements of b[] are
smaller than smallest(or first)
element of a[] or b[] is empty*/
else if (j == n2) {
m2 = m1;
m1 = a[i];
i++;
}
}
/*Below is to handle the case where
sum of number of elements
of the arrays is even */
if ((n1 + n2) % 2 == 0)
return (m1 + m2) * 1.0 / 2;
/* Below is to handle the case where
sum of number of elements
of the arrays is odd */
return m1;
}
// Driver program to test above functions
int main()
{
int a[] = { 1, 12, 15, 26, 38 };
int b[] = { 2, 13, 24 };
int n1 = sizeof(a) / sizeof(a[0]);
int n2 = sizeof(b) / sizeof(b[0]);
printf("%f", findmedian(a, n1, b, n2));
return 0;
}
Java
// A Java program to find median of two sorted arrays of
// unequal sizes
import java.io.*;
class GFG {
// A utility function to find median of two integers
/* This function returns median of a[] and b[].
Assumptions in this function: Both a[] and b[]
are sorted arrays */
static float findmedian(int a[], int n1, int b[], int n2)
{
int i = 0; /* Current index of
i/p array a[] */
int j = 0; /* Current index of
i/p array b[] */
int k;
int m1 = -1, m2 = -1;
for (k = 0; k <= (n1 + n2) / 2; k++) {
if (i < n1 && j < n2) {
if (a[i] < b[j]) {
m2 = m1;
m1 = a[i];
i++;
}
else {
m2 = m1;
m1 = b[j];
j++;
}
}
/* Below is to handle the case where
all elements of a[] are
smaller than smallest(or first)
element of b[] or a[] is empty*/
else if (i == n1) {
m2 = m1;
m1 = b[j];
j++;
}
/* Below is to handle case where
all elements of b[] are
smaller than smallest(or first)
element of a[] or b[] is empty*/
else if (j == n2) {
m2 = m1;
m1 = a[i];
i++;
}
}
/*Below is to handle the case where
sum of number of elements
of the arrays is even */
if ((n1 + n2) % 2 == 0) {
return (m1 + m2) * (float)1.0 / 2;
}
/* Below is to handle the case where
sum of number of elements
of the arrays is odd */
return m1;
}
// Driver program to test above functions
public static void main(String[] args)
{
int a[] = { 1, 12, 15, 26, 38 };
int b[] = { 2, 13, 24 };
int n1 = a.length;
int n2 = b.length;
System.out.println(findmedian(a, n1, b, n2));
}
}
// This code has been contributed by inder_verma.
Python3
# Python3 program to find median of # two sorted arrays of unequal sizes # A utility function to find median # of two integers ''' This function returns median of a[] and b[]. Assumptions in this function: Both a[] and b[] are sorted arrays ''' def findmedian(a, n1, b, n2): i = 0 # Current index of i / p array a[] j = 0 # Current index of i / p array b[] m1 = -1 m2 = -1 for k in range(((n1 + n2) // 2) + 1) : if (i < n1 and j < n2) : if (a[i] < b[j]) : m2 = m1 m1 = a[i] i += 1 else : m2 = m1 m1 = b[j] j += 1 # Below is to handle the case where # all elements of a[] are # smaller than smallest(or first) # element of b[] or a[] is empty elif(i == n1) : m2 = m1 m1 = b[j] j += 1 # Below is to handle case where # all elements of b[] are # smaller than smallest(or first) # element of a[] or b[] is empty elif (j == n2) : m2 = m1 m1 = a[i] i += 1 '''Below is to handle the case where sum of number of elements of the arrays is even ''' if ((n1 + n2) % 2 == 0): return (m1 + m2) * 1.0 / 2 ''' Below is to handle the case where sum of number of elements of the arrays is odd ''' return m1 # Driver Code if __name__ == "__main__": a = [ 1, 12, 15, 26, 38 ] b = [ 2, 13, 24 ] n1 = len(a) n2 = len(b) print(findmedian(a, n1, b, n2)) # This code is contributed # by ChitraNayal
C#
// A C# program to find median
// of two sorted arrays of
// unequal sizes
using System;
class GFG {
// A utility function to find
// median of two integers
/* This function returns
median of a[] and b[].
Assumptions in this
function: Both a[] and b[]
are sorted arrays */
static float findmedian(int[] a, int n1,
int[] b, int n2)
{
int i = 0; /* Current index of
i/p array a[] */
int j = 0; /* Current index of
i/p array b[] */
int k;
int m1 = -1, m2 = -1;
for (k = 0; k <= (n1 + n2) / 2; k++) {
if (i < n1 && j < n2) {
if (a[i] < b[j]) {
m2 = m1;
m1 = a[i];
i++;
}
else {
m2 = m1;
m1 = b[j];
j++;
}
}
/* Below is to handle the case where
all elements of a[] are
smaller than smallest(or first)
element of b[] or a[] is empty*/
else if (i == n1) {
m2 = m1;
m1 = b[j];
j++;
}
/* Below is to handle case where
all elements of b[] are
smaller than smallest(or first)
element of a[] or b[] is empty*/
else if (j == n2) {
m2 = m1;
m1 = a[i];
i++;
}
}
/*Below is to handle the case where
sum of number of elements
of the arrays is even */
if ((n1 + n2) % 2 == 0) {
return (m1 + m2) * (float)1.0 / 2;
}
/* Below is to handle the case
where sum of number of elements
of the arrays is odd */
return m1;
}
// Driver Code
public static void Main()
{
int[] a = { 1, 12, 15, 26, 38 };
int[] b = { 2, 13, 24 };
int n1 = a.Length;
int n2 = b.Length;
Console.WriteLine(findmedian(a, n1, b, n2));
}
}
// This code is contributed
// by Subhadeep Gupta
PHP
<?php
// A PHP program to find median of
// two sorted arrays of unequal sizes
// A utility function to find
// median of two integers
/* This function returns median
of a[] and b[]. Assumptions in this
function: Both a[] and b[] are
sorted arrays */
function findmedian($a, $n1, $b, $n2)
{
$i = 0; /* Current index of
i/p array a[] */
$j = 0; /* Current index of
i/p array b[] */
$k;
$m1 = -1; $m2 = -1;
for ($k = 0;
$k <= ($n1 + $n2) / 2; $k++)
{
if ($i < $n1 and $j < $n2)
{
if ($a[$i] < $b[$j])
{
$m2 = $m1;
$m1 = $a[$i];
$i++;
}
else
{
$m2 = $m1;
$m1 = $b[$j];
$j++;
}
}
/* Below is to handle the case
where all elements of a[] are
smaller than smallest(or first)
element of b[] or a[] is empty*/
else if (i == n1)
{
$m2 = $m1;
$m1 = $b[j];
$j++;
}
/* Below is to handle case
where all elements of b[] are
smaller than smallest(or first)
element of a[] or b[] is empty*/
else if ($j == $n2)
{
$m2 = $m1;
$m1 = $a[$i];
$i++;
}
}
/*Below is to handle the case
where sum of number of elements
of the arrays is even */
if (($n1 + $n2) % 2 == 0)
return ($m1 + $m2) * 1.0 / 2;
/* Below is to handle the case
where sum of number of elements
of the arrays is odd */
return m1;
}
// Driver Code
$a = array( 1, 12, 15, 26, 38 );
$b = array( 2, 13, 24 );
$n1 = count($a);
$n2 = count($b);
echo(findmedian($a, $n1, $b, $n2));
// This code is contributed
// by inder_verma.
?>
Javascript
<script>
// A Javascript program to find median
// of two sorted arrays of unequal sizes
// A utility function to find median of two integers
// This function returns median of a[] and b[].
// Assumptions in this function: Both a[] and b[]
// are sorted arrays
function findmedian(a, n1, b, n2)
{
let i = 0; /* Current index of
i/p array a[] */
let j = 0; /* Current index of
i/p array b[] */
let k;
let m1 = -1, m2 = -1;
for(k = 0; k <= (n1 + n2) / 2; k++)
{
if (i < n1 && j < n2)
{
if (a[i] < b[j])
{
m2 = m1;
m1 = a[i];
i++;
}
else
{
m2 = m1;
m1 = b[j];
j++;
}
}
/* Below is to handle the case where
all elements of a[] are
smaller than smallest(or first)
element of b[] or a[] is empty*/
else if (i == n1)
{
m2 = m1;
m1 = b[j];
j++;
}
/* Below is to handle case where
all elements of b[] are
smaller than smallest(or first)
element of a[] or b[] is empty*/
else if (j == n2)
{
m2 = m1;
m1 = a[i];
i++;
}
}
/*Below is to handle the case where
sum of number of elements
of the arrays is even */
if ((n1 + n2) % 2 == 0)
{
return (m1 + m2) * 1.0 / 2;
}
/* Below is to handle the case where
sum of number of elements
of the arrays is odd */
return m1;
}
// Driver code
let a = [ 1, 12, 15, 26, 38 ];
let b = [ 2, 13, 24 ];
let n1 = a.length;
let n2 = b.length;
document.write(findmedian(a, n1, b, n2));
// This code is contributed by rag2127
</script>
Producción:
14.000000
Análisis de Complejidad:
- Complejidad de tiempo : O (n), ambas listas deben atravesarse para que la complejidad de tiempo sea O (n).
- Espacio Auxiliar: O(1), no se requiere espacio extra.
Más eficiente (métodos de complejidad de tiempo de registro)
- Mediana de dos arreglos ordenados de diferentes tamaños.
- Mediana de dos arrays ordenadas de diferentes tamaños en min (Log (n1, n2))
Publicación traducida automáticamente
Artículo escrito por KogaraNaveenKumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA