两个已排序数组的中位数

Question

两个已排序数组的中位数

14

我的问题与此链接中的方法2有关。在这种方法中，给定两个等长的排序数组，我们需要找到合并后的两个数组的中位数。

Algorithm:

1) Calculate the medians m1 and m2 of the input arrays ar1[] 
   and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
     return m1 (or m2)
3) If m1 is greater than m2, then median is present in one 
   of the below two subarrays.
    a)  From first element of ar1 to m1 (ar1[0...|_n/2_|])
    b)  From m2 to last element of ar2  (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one    
   of the below two subarrays.
   a)  From m1 to last element of ar1  (ar1[|_n/2_|...n-1])
   b)  From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays 
   becomes 2.
6) If size of the two arrays is 2 then use below formula to get 
  the median.
    Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

Example:

   ar1[] = {1, 12, 15, 26, 38}
   ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

   [15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:

    m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become

  [15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
                       = (max(15, 13) + min(26, 17))/2 
                       = (15 + 17)/2
                       = 16

我理解他们是如何排除数组的一半并说中位数会在特定的数组一半中，例如第1,2,3,4,5步。

但是我无法理解，他们怎么能说合并数组的中位数将是修剪数组一半后得到的合并数组的中位数，即{1,12,15,26,38}和{2,13,17,30,45}的合并数组的中位数将是{2,13,17}和{15,26,38}的合并数组的中位数。

请解释一下。先谢谢。

- AvinashK

11个回答

4

...他们如何说合并数组的中位数是在修剪数组一半后得到的合并数组的中位数，即{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）。

- Ely

3

对于变长数组，您只需要检查在递归的每个层次中数组是否仅具有1个元素的特殊情况。如果其中一个是这样，请不要进一步分隔，直接将其传递到另一个数组也变为长度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;
    }
}

- Neil

0

这是我的C#解决方案： 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;
}

- Jagadeesh Bandlamudi

0

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

- Vladimir Ramik

0

由于等长约束，当我们比较两个中位数时，我们可以安全地丢弃一些值。

如果m2大于m1，则我们知道数组二必须包含比数组一更多的大值，因此只要我们从数组2中丢弃相同数量的大值，所有小于m1的小值都不重要。结果将是一个更短的数组，但我们寻找的中位数并没有改变，因为我们已经从两侧平均削减了长度。

这有点像通过双手分开支撑物体，然后慢慢地把它们放在一起，保持物体平衡来找到物体的质心。

- Mikeb

0

Java中两个数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        double find =0;
        ArrayList list =  new ArrayList();
            for(int i =0;i<n1;i++)
                list.add(nums1[i]);
        
                
            for(int j =0;j<n2;j++)
                list.add(nums2[j]);
        Collections.sort(list);
        
        int n = list.size();
        if(n%2 != 0)
        {
            find = (Integer)list.get(n/2);
            
            
        }
        else if(n%2==0){
            find = (Integer)list.get(n/2-1)+(Integer)list.get(n/2);
            find = find/2;
        }
        return find;
        
    }
}

- RAJNISH YADAV

0

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;
  }
}

示例

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

- user6184932

-1

 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];
            }

        }

- Sujeet

-1

Swift解决方案100%可行，已测试

//Given 2 sorted arrays Ar1 and Ar2 of size N each. Merge the given arrays and 
find the sum of the two middle elements of the merged array.

  func sumOfSortedArray(Ar1:[Int], Ar2:[Int],N:Int)->Int{
      var newArray = [Int]()
      newArray.append(contentsOf: Ar1)
      newArray.append(contentsOf: Ar2)
      newArray = newArray.sorted()
      //this is how we can get middle index by total of both array divided by 2 and need to minus 1 because array always start with 0 not 1.
      let middleElementIndex = ((N+N)/2) - 1
      let sum = newArray[middleElementIndex] + newArray[middleElementIndex + 1]
      print(sum)
      return sum
  }

- Mr.Javed Multani

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jayadev · Accepted Answer

让我帮助您形象化它。假设是情况3，同样的论点适用于其他情况。这意味着我们已经确定中位数存在于ar1的前半部分或ar2的后半部分。现在的问题是为什么这些半段的中位数与原始数组的中位数相同，对吧。

因此，将这些相关的半段以排序的方式放在一起，并找到其中位数。现在将其他剩余的半段放回到这个图像中，它们会在哪里。 ar2的前半部分，所有n/2元素必须放在这个新中位数的顶部，而arr1的后半部分，则所有n/2元素必须放在该中位数下方（确切位置对于中位数并不重要）。因此，它仍然是一个中位数，因为上下添加了相等数量的元素。因此，两个新半段的中位数与原始集合的中位数相同。

更精确地说，让我们看看为什么ar2的前半部分（剩余的一半）必须放在新中位数之上。那是因为当我们把所有元素放在一起时，m2必须放在新中位数之上（因为m2 < m1），这意味着ar2的前半部分也必须放在新中位数之上。换句话说，如果m是2个选定半段的新中位数，则m2 < m => ar2的所有前半部分都小于m。ar1的下半部分的类似论点。这意味着新中位数m将保持整个集合的中位数。

更仔细地查看您的算法，虽然方法是正确的，但在处理奇数和偶数情况时，算法可能存在轻微错误，因此在实施时要注意。