12

私の質問は、このリンクの方法 2 に関するものです。ここでは、2 つの等しい長さの並べ替えられた配列が与えられ、マージされた 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

2

可変長の場合、配列のいずれかが再帰の各レベルで 1 つの要素しか持たない特殊なケースを確認する必要があります。それらの1つがそのようなものである場合、それ以上分割しないで、もう1つも長さが2になるまでそのまま渡します。

    //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

Java の 2 つの配列の中央値

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 に答える
-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 に答える
-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 に答える