12

我的问题是参考此链接的方法 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} 的合并数组的中位数。

请解释。提前致谢。

4

11 回答 11

11

让我帮你想象一下。可以说它是案例 3，对于其他案例也遵循相同的论点。这意味着我们已经确定中值存在于 ar1 的前半部分或 ar2 的后半部分。现在的问题是为什么这些一半的中位数与原始数组的中位数相同，对吧。

因此，想象一下将这些相关的部分按排序顺序放在一起并找到它的中值。现在把剩下的一半放回这张照片里，他们会去哪里。ar2 的前半部分，所有 n/2 个元素都必须到达这个新中位数的顶部，而 arr1 的后半部分所有 n/2 个元素都必须低于这个中位数（确切的位置对于中位数并不重要）。所以这意味着它仍然是一个中位数，因为在它的上方和下方添加了相同数量的元素。所以两个新的一半的中位数与原始集合的中位数相同。

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

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

于 2013-09-13T17:08:25.953 回答
3

...他们怎么能说合并数组的中位数将是在修剪数组的一半后产生的合并数组的中位数，即 {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）。

于 2016-05-18T06:13:28.940 回答
2

对于可变长度，您只需检查任何一个数组在每个递归级别中只有 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;
    }
}
于 2016-05-30T16:30:06.303 回答
0

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

如果 m2 大于 m1，我们知道数组 2 必须包含比数组 1 更多的大值，因此只要我们从数组 2 中丢弃相同数量的大值，m1 以下的所有小值都不感兴趣. 结果将是一个更短的数组，但我们正在寻找的中位数没有改变，因为我们已经从两边进行了同样的修剪。

这让我想起了找到一个物体的质心，用你的双手分开支撑它，然后慢慢地将它们放在一起，保持物体平衡。

于 2013-09-13T16:29:36.043 回答
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
于 2017-08-01T02:09:13.700 回答
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;
        
    }
}
于 2020-06-28T16:30:36.013 回答
0

这是我的 C# 解决方案：

公共双 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;
}
于 2018-03-28T07:44:11.797 回答
0

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
  }
于 2021-05-26T19:57:28.373 回答
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
于 2019-08-16T12:55:20.947 回答
-1

@jayadev：我不同意你的回答。
“ ar2 的前半部分，所有 n/2 个元素都必须到达这个新中位数的顶部，而 arr1 的后半部分，所有 n/2 个元素都必须低于这个中位数”

考虑这个测试用例： a1 = {1,2,15,16,17} a2 = {4,5,10,18,20}

于 2014-10-02T12:46:48.230 回答
-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];
            }

        }
于 2015-10-19T21:08:20.587 回答