Рубрики

Медиана двух отсортированных массивов разных размеров

Это расширение медианы двух отсортированных массивов задачи одинакового размера . Здесь мы также обрабатываем массивы неравного размера.

Метод 1: (Линейный и более простой подход)
Здесь нам нужно найти медиану двух отсортированных массивов разных размеров, поэтому мы сохраняем две переменные для указания на массивы и одну для подсчета количества прочитанных элементов. Мы использовали простое решение O (n), основанное на слиянии, просто мы не объединяем массив, а отслеживаем последний прочитанный элемент, пока не достигнем медианы
Есть два случая:
Случай 1: нечетное m + n
Затем мы найдем чистую медиану с индексом (m + n) / 2 в массиве, полученном после объединения обоих массивов, поэтому мы просто пересекаем оба массива и сохраняем последнее значение в m1 после цикла, m1 будет содержать значение медиана
Случай 2: m + n четное
Медиана будет средним для элементов с индексами ((m + n) / 2 — 1) и (m + n) / 2 в массиве, полученном после объединения обоих массивов, поэтому нам нужно отслеживать не только последний элемент, но и второй последний элемент (для этого используется m2), поэтому мы пересекаем оба массива и сохраняем последнее значение в m1 и второе последнее значение в m2 после цикла, (m1 + m2) / 2 будет содержать значение медианы.

Ниже приведена реализация вышеуказанного подхода:

C ++

// Простое решение на основе слияния O (n) для поиска
// медиана двух отсортированных массивов
#include <bits/stdc++.h>

using namespace std;

  
/ * Эта функция возвращает медиану ar1 [] и ar2 [].
Предположение в этой функции:
И ar1 [], и ar2 [] являются отсортированными массивами * /

int getMedian(int ar1[], int ar2[], int n, int m) 

    int i = 0; / * Текущий индекс входного массива ar1 [] * /

    int j = 0; / * Текущий индекс входного массива ar2 [] * /

    int count; 

    int m1 = -1, m2 = -1; 

  

    // Поскольку существует (n + m) элементов,

    // Есть два следующих случая

    // если n + m нечетно, то середина

    // индекс является медианным, т.е. (m + n) / 2

    if((m + n) % 2 == 1) 

    

        for (count = 0; count <= (n + m)/2; count++)

        

            if(i != n && j != m)

            

                m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++]; 

            

            else if(i < n)

            

                m1 = ar1[i++]; 

            

            // для случая, когда j <m,

            else

            

                m1 = ar1[j++]; 

            

        

        return m1; 

    

      

    // медиана будет средним из элементов

    // по индексу ((m + n) / 2 - 1) и (m + n) / 2

    // в массиве, полученном после объединения ar1 и ar2

    else 

    

        for (count = 0; count <= (n + m)/2; count++) 

        

            m2 = m1; 

            if(i != n && j != m)

            

                m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++]; 

            

            else if(i < n)

            

                m1 = ar1[i++]; 

            

            // для случая, когда j <m,

            else

            

                m1 = ar1[j++]; 

            

        

        return (m1 + m2)/2; 

    

  
/ * Код водителя * /

int main() 

    int ar1[] = {900}; 

    int ar2[] = {5, 8, 10, 20}; 

  

    int n1 = sizeof(ar1)/sizeof(ar1[0]); 

    int n2 = sizeof(ar2)/sizeof(ar2[0]); 

    cout << getMedian(ar1, ar2, n1, n2); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// Простое решение на основе слияния O (n) для поиска
// медиана двух отсортированных массивов
#include <stdio.h> 

  
/ * Эта функция возвращает медиану ar1 [] и ar2 [].
Предположение в этой функции:
И ar1 [], и ar2 [] являются отсортированными массивами * /

int getMedian(int ar1[], int ar2[], int n, int m) 

    int i = 0; / * Текущий индекс входного массива ar1 [] * /

    int j = 0; / * Текущий индекс входного массива ar2 [] * /

    int count; 

    int m1 = -1, m2 = -1; 

  

    // Поскольку существует (n + m) элементов,

    // Есть два следующих случая

    // если n + m нечетно, то середина

    // индекс является медианным, т.е. (m + n) / 2

    if((m + n) % 2 == 1) {

        for (count = 0; count <= (n + m)/2; count++) {

            if(i != n && j != m){

            m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];

            }

            else if(i < n){

            m1 = ar1[i++];

            }

            // для случая, когда j <m,

            else{

            m1 = ar2[j++];

            }

        }

        return m1;

    }

      

    // медиана будет средним из элементов

    // по индексу ((m + n) / 2 - 1) и (m + n) / 2

    // в массиве, полученном после объединения ar1 и ar2

    else {

        for (count = 0; count <= (n + m)/2; count++) {

            m2 = m1;

            if(i != n && j != m){

            m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];

            }

            else if(i < n){

            m1 = ar1[i++];

            }

            // для случая, когда j <m,

            else{

            m1 = ar1[j++];

            }

        }

        return (m1 + m2)/2;

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main() 

    int ar1[] = {900}; 

    int ar2[] = {5, 8, 10, 20}; 

  

    int n1 = sizeof(ar1)/sizeof(ar1[0]); 

    int n2 = sizeof(ar2)/sizeof(ar2[0]); 

    printf("%d", getMedian(ar1, ar2, n1, n2)); 

    getchar(); 

    return 0; 


// Этот код загружен Pratil


Выход:

 10 

Метод 2: (Эффективный, но немного сложный подход)
Подход, обсуждаемый в этом посте, аналогичен методу 2 поста равного размера . Основная идея та же: мы находим медиану двух массивов и сравниваем медианы, чтобы отбросить почти половину элементов в обоих массивах. Поскольку количество элементов здесь может различаться, существует много базовых случаев, которые необходимо обрабатывать отдельно. Прежде чем мы приступим к завершению решения, давайте сначала поговорим обо всех базовых случаях.

Пусть двумя массивами будут A [N] и B [M]. В следующем объяснении предполагается, что N меньше или равно M.

Базовые случаи:
Меньший массив имеет только один элемент
Случай 0: N = 0, M = 2
Случай 1: N = 1, M = 1.
Случай 2: N = 1, М нечетное
Случай 3: N = 1, М четное
Меньший массив имеет только два элемента
Случай 4: N = 2, M = 2
Случай 5: N = 2, M нечетно
Случай 6: N = 2, M четное

Случай 0: в первом массиве нет элементов, возвращающих медиану второго массива. Если второй массив также пуст, вернуть -1.

Случай 1: В обоих массивах есть только один элемент, поэтому выведите среднее значение A [0] и B [0].

Случай 2: N = 1, М нечетное
Пусть B [5] = {5, 10, 12, 15, 20}
Сначала найдите средний элемент B [], который равен 12 для вышеуказанного массива. Есть следующие 4 подслоя.
2.1 Если A [0] меньше 10, медиана составляет 10 и 12.
2.2 Если A [0] лежит между 10 и 12, медиана является средней от A [0] и 12.
2.3 Если A [0] лежит между 12 и 15, медиана составляет в среднем 12 и A [0].
2.4 Если A [0] больше 15, медиана составляет в среднем 12 и 15.
Во всех подслоях мы находим, что 12 фиксировано. Итак, нам нужно найти медиану B [M / 2 — 1], B [M / 2 + 1], A [0] и взять ее среднее значение с помощью B [M / 2].

Случай 3: N = 1, М четное
Пусть B [4] = {5, 10, 12, 15}
Сначала найдите средние элементы в B [], которые в приведенном выше примере равны 10 и 12. Есть следующие 3 подслоя.
3.1 Если A [0] меньше 10, медиана равна 10.
3.2 Если A [0] лежит между 10 и 12, медиана равна A [0].
3.3 Если A [0] больше 12, медиана равна 12.
Итак, в этом случае найдите медиану трех элементов B [M / 2 — 1], B [M / 2] и A [0].

Случай 4: N = 2, M = 2
Всего четыре элемента. Итак, мы находим медиану из 4 элементов.

Случай 5: N = 2, M нечетно
Пусть B [5] = {5, 10, 12, 15, 20}
Медиана определяется медианой следующих трех элементов: B [M / 2], max (A [0], B [M / 2 — 1]), min (A [1], B [M / 2 + 1] ).

Случай 6: N = 2, M четное
Пусть B [4] = {5, 10, 12, 15}
Медиана определяется медианой следующих четырех элементов: B [M / 2], B [M / 2 — 1], max (A [0], B [M / 2 — 2]), min (A [1] , B [M / 2 + 1])

Остальные случаи:
После того, как мы обработали вышеперечисленные базовые случаи, последующим является следующий процесс.
1) Найдите средний элемент A [] и средний элемент B [].
… .. 1.1) Если средний элемент A [] больше среднего элемента B [], игнорируйте последнюю половину A [], пусть длина игнорируемой части равна idx. Кроме того, вырежьте B [] по idx с самого начала.
… .. 1.2) иначе, игнорируйте первую половину A [], пусть длина игнорируемой части равна idx. Также вырежьте B [] по idx из последнего.

Ниже приводится реализация вышеуказанного подхода.

C ++

// Программа на C ++ для поиска медианы двух отсортированных массивов
// неравные размеры
#include <bits/stdc++.h>

using namespace std;

  
// Полезная функция для поиска медианы двух целых

float MO2(int a, int b)

{ return ( a + b ) / 2.0; }

  
// Полезная функция для нахождения медианы трех целых

float MO3(int a, int b, int c)

{

    return a + b + c - max(a, max(b, c))

                     - min(a, min(b, c));

}

  
// Полезная функция для поиска медианы из четырех целых чисел

float MO4(int a, int b, int c, int d)

{

    int Max = max( a, max( b, max( c, d ) ) );

    int Min = min( a, min( b, min( c, d ) ) );

    return ( a + b + c + d - Max - Min ) / 2.0;

}

  
// Сервисная функция для поиска медианы одного массива

float medianSingle(int arr[], int n)

{

   if (n == 0)

      return -1;

   if (n%2 == 0)

        return (double)(arr[n/2] + arr[n/2-1])/2;

   return arr[n/2];

}

  
// Эта функция предполагает, что N меньше или равно M
// Эта функция возвращает -1, если оба массива пусты

float findMedianUtil( int A[], int N, int B[], int M )

{

    // Если меньший массив пуст, вернуть медиану из второго массива

    if (N == 0)

      return medianSingle(B, M);

  

    // Если меньший массив имеет только один элемент

    if (N == 1)

    {

        // Случай 1: если массив большего размера также имеет один элемент,

        // просто вызываем MO2 ()

        if (M == 1)

            return MO2(A[0], B[0]);

  

        // Случай 2: если массив большего размера имеет нечетное количество элементов,

        // затем рассмотрим 3 средних элемента большего массива и

        // единственный элемент меньшего массива. Возьми несколько примеров

        // вроде следующего

        // A = {9}, B [] = {5, 8, 10, 20, 30} и

        // A [] = {1}, B [] = {5, 8, 10, 20, 30}

        if (M & 1)

            return MO2( B[M/2], MO3(A[0], B[M/2 - 1], B[M/2 + 1]) );

  

        // Случай 3: если у большего массива четное число элементов,

        // тогда медиана будет одним из следующих 3 элементов

        // ... средние два элемента большего массива

        // ... единственный элемент меньшего массива

        return MO3( B[M/2], B[M/2 - 1], A[0] );

    }

  

    // Если меньший массив имеет два элемента

    else if (N == 2)

    {

        // Случай 4: если массив большего размера также имеет два элемента,

        // просто вызываем MO4 ()

        if (M == 2)

            return MO4(A[0], A[1], B[0], B[1]);

  

        // Случай 5: если в большем массиве нечетное количество элементов,

        // тогда медиана будет одним из следующих 3 элементов

        // 1. Средний элемент большего массива

        // 2. Макс первого элемента меньшего массива и элемента

        // перед серединой в большем массиве

        // 3. Минус второго элемента меньшего массива и элемента

        // сразу после середины в большем массиве

        if (M & 1)

            return MO3 ( B[M/2],

                         max(A[0], B[M/2 - 1]),

                         min(A[1], B[M/2 + 1])

                       );

  

        // Случай 6: если в большем массиве четное количество элементов,

        // тогда медиана будет одним из следующих 4 элементов

        // 1) & 2) Средние два элемента большего массива

        // 3) Макс первого элемента меньшего массива и элемента

        // перед первым средним элементом в большем массиве

        // 4. Минус второго элемента меньшего массива и элемента

        // сразу после второй середины в большем массиве

        return MO4 ( B[M/2],

                     B[M/2 - 1],

                     max( A[0], B[M/2 - 2] ),

                     min( A[1], B[M/2 + 1] )

                   );

    }

  

    int idxA = ( N - 1 ) / 2;

    int idxB = ( M - 1 ) / 2;

  

     / * если A [idxA] <= B [idxB], то медиана должна существовать в

        A [idxA ....] и B [.... idxB] * /

    if (A[idxA] <= B[idxB] )

      return findMedianUtil(A + idxA, N/2 + 1, B, M - idxA );

  

    / * если A [idxA]> B [idxB], то медиана должна существовать в

       A [... idxA] и B [idxB ....] * /

    return findMedianUtil(A, N/2 + 1, B + idxA, M - idxA );

}

  
// Функция-обертка для findMedianUtil (). Эта функция
// гарантирует, что меньший массив передается в качестве первого аргумента
// to findMedianUtil

float findMedian( int A[], int N, int B[], int M )

{

    if (N > M)

       return findMedianUtil( B, M, A, N );

  

    return findMedianUtil( A, N, B, M );

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int A[] = {900};

    int B[] = {5, 8, 10, 20};

  

    int N = sizeof(A) / sizeof(A[0]);

    int M = sizeof(B) / sizeof(B[0]);

  

    printf("%f", findMedian( A, N, B, M ) );

    return 0;

}

PHP

<?php
// PHP программа для поиска медианы
// из двух отсортированных массивов
// неравные размеры

  
// Функция полезности для
// найти медиану из двух целых

function MO2($a, $b)

    return ($a + $b) / 2.0;

}

  
// Функция полезности для
// найти медиану из трех целых

function MO3($a, $b, $c)

{

    return $a + $b + $c

       max($a, max($b, $c)) -

       min($a, min($b, $c));

}

  
// Полезная функция для поиска
// медиана из четырех целых

function MO4($a, $b, $c, $d)

{

    $Max = max($a, max($b, max($c, $d)));

    $Min = min($a, min($b, min( $c, $d)));

    return ($a + $b + $c + $d - $Max - $Min) / 2.0;

}

  
// Функция полезности для
// найти медиану одного массива

function medianSingle($arr, $n)

{

if ($n == 0)

    return -1;

if ($n % 2 == 0)

        return ($arr[$n / 2] + 

                $arr[$n / 2 - 1]) / 2;

return $arr[$n / 2];

}

  
// Эта функция предполагает, что N
// меньше или равно M
// Эта функция возвращает -1, если
// оба массива пусты

function findMedianUtil(&$A, $N, &$B, $M )

{

    // Если меньший массив пуст,

    // вернуть медиану из второго массива

    if ($N == 0)

    return medianSingle($B, $M);

  

    // Если меньший массив

    // имеет только один элемент

    if ($N == 1)

    {

        // Случай 1: если больше

        // массив также имеет

        // элемент, просто вызовите MO2 ()

        if ($M == 1)

            return MO2($A[0], $B[0]);

  

        // Случай 2: если массив больше

        // имеет нечетное количество элементов,

        // тогда рассмотрим середину 3

        // элементы большего массива и

        // единственный элемент меньшего размера

        // массив. Возьми несколько примеров

        // вроде следующего

        // $ A = array (9),

        // $ B = массив (5, 8, 10, 20, 30)

        // и $ A = array (1),

        // $ B = массив (5, 8, 10, 20, 30)

        if ($M & 1)

            return MO2($B[$M / 2], $MO3($A[0], 

                       $B[$M / 2 - 1], 

                       $B[$M / 2 + 1]));

  

        // Случай 3: если массив больше

        // имеет четный номер элемента,

        // тогда медиана будет одним из

        // следующие 3 элемента

        // ... средние два элемента

        // большего массива

        // ... Единственный элемент

        // меньший массив

        return MO3($B[$M / 2], 

                   $B[$M / 2 - 1], $A[0]);

    }

  

    // Если меньший массив

    // имеет два элемента

    else if ($N == 2)

    {

        // Случай 4: если больше

        // массив также имеет два элемента,

        // просто вызываем MO4 ()

        if ($M == 2)

            return MO4($A[0], $A[1],

                       $B[0], $B[1]);

  

        // Случай 5: если массив больше

        // имеет нечетное количество элементов,

        // тогда медиана будет одним из

        // следующие 3 элемента

        // 1. Средний элемент

        // больший массив

        // 2. Макс первого элемента

        // меньший массив и элемент

        // прямо перед серединой

        // в большем массиве

        // 3. Минус второго элемента

        // меньшего массива и элемента

        // сразу после середины

        // в большем массиве

        if ($M & 1)

            return MO3 ($B[$M / 2],

                        max($A[0], $B[$M / 2 - 1]),

                        min($A[1], $B[$M / 2 + 1]));

  

        // Случай 6: если массив больше

        // имеет четное количество элементов,

        // тогда медиана будет одним из

        // следующие 4 элемента

        // 1) и 2) Средние два

        // элементы большего массива

        // 3) Макс первого элемента

        // меньший массив и элемент

        // как раз перед первой серединой

        // элемент в большем массиве

        // 4. Минус второго элемента

        // меньший массив и элемент

        // сразу после второго

        // середина в большем массиве

        return MO4 ($B[$M / 2],

                    $B[$M / 2 - 1],

                    max($A[0], $B[$M / 2 - 2]),

                    min($A[1], $B[$M / 2 + 1]));

    }

  

    $idxA = ($N - 1 ) / 2;

    $idxB = ($M - 1 ) / 2;

  

    / * если $ A [$ idxA] <= $ B [$ idxB], то

        Медиана должна существовать в

        $ A [$ idxA ....] и $ B [.... $ idxB] * /

    if ($A[$idxA] <= $B[$idxB] )

    return findMedianUtil($A + $idxA

                          $N / 2 + 1, $B

                          $M - $idxA );

  

    / * если $ A [$ idxA]> $ B [$ idxB],

    тогда медиана должна существовать в

    $ A [... $ idxA] и $ B [$ idxB ....] * /

    return findMedianUtil($A, $N/2 + 1, 

                          $B + $idxA, $M - $idxA );

}

  
// Обертка вокруг функции
// findMedianUtil (). Эта
// функция гарантирует, что
// меньший массив передается как
// первый аргумент для findMedianUtil

function findMedian(&$A, $N

                    &$B, $M )

{

    if ($N > $M)

    return findMedianUtil($B, $M

                          $A, $N );

  

    return findMedianUtil($A, $N

                          $B, $M );

}

  
// Код драйвера

$A = array(900);

$B = array(5, 8, 10, 20);

  

$N = sizeof($A);

$M = sizeof($B);

  

echo findMedian( $A, $N, $B, $M );

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

 10 

Сложность времени: O (LogM + LogN)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Медиана двух отсортированных массивов разных размеров

0.00 (0%) 0 votes