【LeetCode】#004,2つの秩序配列の中位数を探す

2552 ワード

一、テーマの説明
mとnのサイズの2つの秩序配列nums 1とnums 2が与えられる.この2つの秩序配列の中位数を見つけ,アルゴリズムの時間的複雑さをO(log(m+n))とすることを要求してください.nums 1とnums 2が同時に空にならないと仮定できます.
二、問題を解く
中位数:データのグループの中で中間位置にある数で、サンプル、クラスタ、または確率分布の数値を表します.数値のセットを等しい上下の2つの部分に分割できます.
この問題は本当に難しいですね.アルゴリズムの時間の複雑さはそこに要求されていますから、答えを出せばいいというわけではありません.最適解が必要です.こちらはleetcodeのある大神のスクリーンショットの考え方を参考にして、私の理解を加えて出力をなくしました.
三、ソースコード
    public static void main(String[] args) {
        int nums1[] = {2, 7, 11, 15};
        int nums2[] = {3, 7, 8, 14, 45};
        double result = findMedianSortedArrays(nums1, nums2);
        System.out.println("result:" + result);
    }


    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;//    1   
        int m = nums2.length;//    2   
        int odd = (n + m + 1) / 2;//        ,      
        int even = (n + m + 2) / 2;//        ,      
        //           ,     ,        k 。
        return (getNth(nums1, 0, n - 1, nums2, 0, m - 1, odd) + getNth(nums1, 0, n - 1, nums2, 0, m - 1, even)) *0.5;
    }

    /**
     *    n   ,        
     *
     * @param nums1    1
     * @param start1      
     * @param end1        
     * @param nums2    2
     * @param start2      
     * @param end2        
     * @param n
     * @return
     */
    private static int getNth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int n) {
        int len1 = end1 - start1 + 1;//         1  
        int len2 = end2 - start2 + 1;//         2  
        //  len1       len2,             ,    len1
        if (len1 > len2) return getNth(nums2, start2, end2, nums1, start1, end1, n);
        //   1           ,      2  N   
        if (len1 == 0) return nums2[start2 + n - 1];
        // n  1 ,            ,                     
        if (n == 1) return Math.min(nums1[start1], nums2[start2]);
        //            ,
        int i = start1 + Math.min(len1, n / 2) - 1;
        int j = start2 + Math.min(len2, n / 2) - 1;
        //    1  i    2  j   。
        //    1   i     ,    2 j               ,     2       j+1     。
        if (nums1[i] > nums2[j]) {
            //       n   ,    ,n=n-    -1。
            return getNth(nums1, start1, end1, nums2, j + 1, end2, n - (j - start2 + 1));
        }
        //    2   j         。
        else {
            return getNth(nums1, i + 1, end1, nums2, start2, end2, n - (i - start1 + 1));
        }
    }
}

四、githubを添付
https://github.com/maryyMa/LeetCodeTest/commit/86bef193c607f6c2ed553118af74d1eb61550852