Ответ 1

Позвольте мне помочь вам визуализировать его. Допустим, что это случай 3, тот же аргумент следует для другого случая. Это означает, что мы определили, что медиана присутствует в первой половине ar1 или второй половины ar2. Теперь вопрос в том, почему медиана этих половин такая же, как медиана исходных массивов, правильно.

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

Чтобы быть более точным, давайте посмотрим, почему первая половина ar2 (оставшаяся половина) должна выйти выше новой медианы. Это так, потому что, когда мы помещаем все элементы вместе m2, нужно идти выше новой медианы (так как m2 < m1), что означает, что вся первая половина ar2 также должна превышать новую медиану. Другими словами, если m представляет собой новую медиану из двух выбранных половинок, m2 < m = > вся первая половина ar2 < м. Аналогичный аргумент для нижней половины ar1. Это означает, что новая медиана m останется медианной для всего набора.

Глядя более внимательно на ваш алгоритм, хотя подход правильный, может возникнуть небольшая ошибка в алгоритме, заботясь о нечетных и четных случаях, поэтому будьте осторожны при реализации.

Ответ 2

... как они могут сказать, что медиана объединенные массивы будут срединными для объединенных массивов, которые будут получены после обрезание половинок массивов, то есть медиану массива слияния {1, 12, 15, 26, 38} и {2, 13, 17, 30, 45} будут медианными слияние массива {2,13,17} и {15, 26, 38}.

Это связано с тем неравенством, которое вы использовали для обрезания половинок и по определению медианы. Медиана разбивает набор упорядоченных чисел в две половины. Вы знаете, что 15 <= 17 (медиана первого набора меньше или равна медиане второго набора), и поэтому медиана должна быть между этими двумя значениями. Все, что меньше 15, обрезается, а что-то большее, чем 17, обрезается, потому что они не могут содержать медианное значение (поскольку они не разделяют набор на две половины). И затем вы применяете те же шаги к более узкому набору; после обрезания вы уменьшили вдвое размер вашего поиска.

Я пытаюсь представить его для этого примера. Соответствующие медианы отмечены символом *, за исключением базового случая, в котором * обозначает числа, используемые для вычисления медианы в этом примере.

1   12   *15*   26    38        2    13   *17*   30  45

          15   *26*   38        2   *13*   17

         *15*   26                   13   *17*           <-- base case

                           16

Существуют и другие базовые случаи, хотя и несколько. Если вы учитываете все базовые случаи, вы можете гарантировать, что алгоритм завершится и вернет правильную медиану.

Я предположил, что медиана - это вычисленное число, которое разделяет набор на две половины.
Когда общее множество имеет нечетное число элементов, медиана является числом этого множества. Но в случае равномерности иногда вы находите, что он рассчитан так, как я показал в этом примере (но иногда выбирается меньший элемент, если вам нужно обеспечить, чтобы медиана была из набора, и в этом случае это было бы 15).

Ответ 3

Для переменной длины вам просто нужно проверить особые случаи, когда любой из массивов имеет только один элемент на каждом уровне рекурсии. Если один из них такой, не делите дальше, просто передайте его так, как он есть до тех пор, пока другой не станет длиной 2. При предоставлении окончательного ответа обрабатывайте случай, когда один из них имеет только 1 элемент.

    //Median of two sorted arrays
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception {
        int[] A = {1, 3, 11};
        int[] B = {2, 4, 12, 14, 15};
        System.out.println("Ans. "+findMedian(A, B));
        //System.out.println(median(A));
    }

    private static int findMedian(int[] A, int[] B) {
        System.out.println(Arrays.toString(A)+" --- "+ Arrays.toString(B));
        int sA = A.length;
        int sB = B.length;

        if(sA <= 2 && sB <= 2) {
            if(sA <= 1 && sA <= 1) {
                return (A[0]+B[0])/2; 
            } else if(sA <= 1) {
                return (max(A[0], B[0]) + min(A[0], B[1])) / 2;
            } else if(sB <= 1) {
                return (max(A[0], B[0]) + min(A[1], B[0]) ) / 2;
            } else {
                System.out.println("xxx");
                return (max(A[0], B[0]) + min(A[1],B[1])) / 2;
            }
        }

        int mA = median(A);
        int mB = median(B);

        if(mA == mB) {
            return mA;
        } else if(mA < mB) {
            if(sA <= 2) {
                return findMedian(A, Arrays.copyOfRange(B, 0, sB/2+1));     
            } else if(sB <= 2) {
                return findMedian(Arrays.copyOfRange(A, sA/2, sA), B); 
            } else {
                return findMedian(Arrays.copyOfRange(A, sA/2, sA)
                          ,Arrays.copyOfRange(B, 0, sB/2+1)); 
            }
        } else {
            if(sA <= 2) {
                return findMedian(A, Arrays.copyOfRange(B, sB/2, sB));  
            } else if(sB <= 2) {
                return findMedian(Arrays.copyOfRange(A, 0, sA/2+1),B); 
            } else {
                return findMedian(Arrays.copyOfRange(A, 0, sA/2+1)
                          ,Arrays.copyOfRange(B, sB/2, sB)); 
            }
        }
    }

    private static int median(int[] A) {
        int size = A.length;
        if(size == 0 ){
            return 0;
        } else if(size == 1) {
            return A[0];
        }

        if(size%2 == 0 ) {
            return (A[size/2 -1 ] + A[size/2  ])/2;
        }else {
            return A[size/2];
        }
    }

    private static int max(int a, int b) {
        return a > b ? a : b;
    }

    private static int min(int a, int b) {
        return a < b ? a : b;
    }
}

Ответ 4

Решение Javascript для нахождения медианы двух отсортированных массивов:

const findMedian = (arr1, arr2) => {
  const len = arr1.length + arr2.length;
  return len % 2 ? oddMedian(Math.floor(len/2), arr1, arr2) : evenMedian((len/2)-1, len/2, arr1, arr2);
}

const oddMedian = (medianIndex, arr1, arr2) => {
  if (arr1[arr1.length-1] < arr2[0]) {
    if (arr1.length > medianIndex) {
      return arr1[medianIndex];
    } else if (arr1.length <= medianIndex) {
      return arr2[medianIndex - arr1.length];
    }
  } else if (arr2[arr2.length-1] < arr1[0]) {
    if (arr2.length > medianIndex) {
      return arr2[medianIndex];
    } else if (arr2.length <= medianIndex) {
      return arr1[medianIndex - arr2.length];
    }
  } else {
    const [shorterArr, largerArr] = arr1.length < arr2.length ? [arr1, arr2] : [arr2, arr1];
    let j = 0;
    let k = 0;
    const sortedArr = [];
    for (let i = 0; i <= medianIndex; i++) {
      if (shorterArr[j] <= largerArr[k]) {
        sortedArr[i] = shorterArr[j];
        j++;
      } else {
        sortedArr[i] = largerArr[k];
        k++;
      }
    }
    return sortedArr[medianIndex];
  }
}

const evenMedian = (medianIndex1, medianIndex2, arr1, arr2) => {
  if (arr1[arr1.length-1] < arr2[0]) {
    if (arr1.length-1 >= medianIndex2) {
      return (arr1[medianIndex1]+arr1[medianIndex2])/2;
    } else if (arr1.length-1 < medianIndex1) {
      const firstMedianIndex = medianIndex1 - arr1.length;
      return (arr2[firstMedianIndex]+arr2[firstMedianIndex+1])/2;
    } else {
      return (arr1[arr1.length-1] + arr2[0])/2;
    }
  } else if (arr2[arr2.length-1] < arr1[0]) {
    if (arr2.length-1 >= medianIndex2) {
      return (arr2[medianIndex1]+arr2[medianIndex2])/2;
    } else if (arr2.length-1 < medianIndex1) {
      const firstMedianIndex = medianIndex1 - arr2.length;
      return (arr1[firstMedianIndex]+arr1[firstMedianIndex+1])/2;
    } else {
      return (arr2[arr2.length-1] + arr1[0])/2;
    }
  } else {
    const [shorterArr, largerArr] = arr1.length < arr2.length ? [arr1, arr2] : [arr2, arr1];
    let i = 0;
    let j = 0;
    let k = 0;
    const sortedArr = [];
    for (let i = 0; i <= medianIndex2; i++) {
      if (shorterArr[j] <= largerArr[k]) {
        sortedArr.push(shorterArr[j]);
        j++;
      } else {
        sortedArr.push(largerArr[k]);
        k++;
      }
    }
    return (sortedArr[medianIndex1] + sortedArr[medianIndex2])/2;
  }
}

Example

console.log("Result:", findMedian([1,3,5], [2,4,6,8]));
console.log("Result:", findMedian([1,3,5,7,10], [2,4,6,8]));
console.log("Result:", findMedian([1,3,5,7,10], [2,4,6,8,9]));
console.log("Result:", findMedian([1,3,5], [2,4,6,8,9]));
console.log("Result:", findMedian([1,3,5,7], [2,4,6,8,9,10]));
console.log("Result:", findMedian([1,3,5,7,10], [2,4,6]));
console.log("Result:", findMedian([1,3,5,7], [2,4]));
console.log("Result:", findMedian([1,2,4], [3,5,6,7,8,9,10,11]));
console.log("Result:", findMedian([1], [2, 3, 4]));
console.log("Result:", findMedian([1, 2], [3, 4]));
console.log("Result:", findMedian([1], [2, 3]));

Выход

Result: 4
Result: 5
Result: 5.5
Result: 4.5
Result: 5.5
Result: 4.5
Result: 3.5
Result: 6
Result: 2.5
Result: 2.5
Result: 2

Ответ 5

Из-за ограничения равной длины, когда мы сравниваем два медианы, мы можем смело отказаться от значений.

Если m2 больше m1, мы знаем, что массив два должен содержать большее количество больших значений, чем массив один, и поэтому все малые значения ниже m1 не интересны, если мы отбросим равное количество больших значений из массива 2. Результат будет более коротким, но медиана, которую мы ищем, не изменилась, так как мы обрезали одинаково с обеих сторон.

Это напоминает мне о том, как найти центр массы объекта, поддерживая его руками далеко друг от друга, а затем медленно сближая их, сохраняя объект сбалансированным.

Ответ 6

Решение PHP:

function Solve( $aArrayOne, $aArrayTwo )
{
    // Base case
    if( empty( $aArrayOne ) || empty( $aArrayTwo ) )
    {
        return false;
    }
    $iCountOne      = count( $aArrayOne );
    $iCountTwo      = count( $aArrayTwo );

    // Single value arrays base case
    if( $iCountOne === 1 && $iCountOne === $iCountTwo )
    {
        return ( $aArrayOne[ 0 ] + $aArrayTwo[ 0 ] ) / 2;
    }

    $iTotalElements = $iCountOne + $iCountTwo;
    $iHalfElements = floor( $iTotalElements / 2 );
    $aPartial       = [];
    $n              = 0;
    // Append elements to new combined array until midway point
    while( $n <= $iHalfElements )
    {
        // Compared both of the first elements to get the 
        // smallest one into the partial array
        if( $aArrayOne[ 0 ] <= $aArrayTwo[ 0 ] )
        {
            $aPartial[] = array_shift( $aArrayOne );
        }
        else
        {
            $aPartial[] = array_shift( $aArrayTwo );
        }
        ++$n;
    }
    // Check to see if we have an odd or an even array for final element math.
    $bIsOddAndPrecise = $iTotalElements % 2;
    $iMedian = ( $bIsOddAndPrecise ) 
    ? $aPartial[ $n - 1 ] 
    : ( $aPartial[ $n - 1 ] + $aPartial[ $n - 2 ] ) / 2;
    return $iMedian;
}

Использованные случаи тестирования:

// $aArrayOne = [1, 3, 4 ];
// $aArrayTwo = [1, 2, 3 ];
// EXPECTED 1,1,2,3,3,4 -> (2+3)/2 2.5
// $aArrayOne = [1, 3, 4, 7, 8, 11, 44, 55, 62];
// $aArrayTwo = [2, 4, 5, 7, 33, 56, 77];
// Expected: 1,2,3,4,4,5,7,7,8,11,33,44,55,56,62,77 -> (7+8)/2 7.5
// $aArrayOne = [1, 3, 4 ];
// $aArrayTwo = [ 100, 100];
// EXPECTED 1,3,4,100,100 -> 4
// $aArrayOne = [1,5,8,10];
// $aArrayTwo = [7,9,14,];
// EXPECTED 1,2,7,8,9,10,14 - > 8
// $aArrayOne = [1,5,8,10];
// $aArrayTwo = [7];
// EXPECTED 1,5,7,8,10 - > 7
// $aArrayOne = [1,5,10];
// $aArrayTwo = [50, 50];
// EXPECTED 1,5,10,50,50 - > 10
// $aArrayOne = [50, 50];
// $aArrayTwo = [1,5,10];
// EXPECTED 1,5,10,50,50 - > 10
// $aArrayOne = [1];
// $aArrayTwo = [1];
// EXPECTED-> 1
// $aArrayOne = [100, 100];
// $aArrayTwo = [100];
// EXPECTED -> 100

Ответ 7

Это мое решение на С#:

public double FindMedianSortedArrays (int [] nums1, int [] nums2) {

    List<int> sorted = new List<int>();

    if(nums1.Length>nums2.Length){
        for(int i=0; i<nums1.Length; i++){

            sorted.Add(nums1[i]);

            if(i<nums2.Length)
                sorted.Add(nums2[i]);
        }
    }
    else{
        for(int i=0; i<nums2.Length; i++){

            sorted.Add(nums2[i]);

            if(i<nums1.Length)
                sorted.Add(nums1[i]);
        }
    }

    sorted.Sort();

    if(sorted.Count % 2 !=0)
       return (double)sorted[sorted.Count/2];

       return (double)(sorted[sorted.Count/2-1]+ sorted[sorted.Count/2])/2;
}

Ответ 8

@jayadev: Я не согласен с вашим ответом. " Первая половина ar2, все n/2 элементы должны перейти в начало этой новой медианы и второй половины arr1, все n/2 элементы должны будут идти ниже этой медианной"

Рассмотрим этот тестовый пример: a1 = {1,2,15,16,17} a2 = {4,5,10,18,20}

Ответ 9

 Here is a very simple solution. 
 Actually it need to merger two sorted array and then find the middle.

        import java.util.Arrays;


        public class MedianofTwoArray {

            /**
             * @param args
             */
            public static void main(String[] args) {

                int []array1= {1,2,3,4,5};
                int []array2= {6,7,8,9,10};
                int median;
                median=findMedian(array1,array2);
                System.out.println(median);

            }

            public static int findMedian(int []arr1,int []arr2) {       
                int [] tempArr=new int[arr1.length+arr2.length]; //creating an array of the length ,equals to sum of arr1 and arr2
                int i=0;
                int j=0;
                int k=0;

                while(i<arr1.length&&j<arr2.length) { /*comparing elements of the two arrays and copying the smaller one into tempArr and
                 incrementing the index of the array from which value is copied */
                    if(arr1[i]<=arr2[j]) {
                        tempArr[k]=arr1[i];

                        i++;
                    }else {
                        tempArr[k]=arr2[j];

                        j++;
                    }
                    k++;
                }
                //copying the left over elements from both arrays
                if(i==arr1.length) {
                    while(j<arr2.length) {
                    tempArr[k]=arr2[j];
                    j++;
                    k++;
                    }
                }else {
                    while(i<arr1.length) {
                        tempArr[k]=arr2[j];
                        j++;
                        k++;
                        }

                }
                System.out.println(Arrays.toString(tempArr));
                return tempArr[tempArr.length/2];
            }

        }