[LintCode/LeetCode] Median of two Sorted Arrays

vvpvvp 發(fā)布于2019-08-14 15:41 / 1836人閱讀

摘要：由于要求的時(shí)間，所以選擇二分法。思路是找到兩個(gè)數(shù)組合并起來(lái)的第個(gè)元素。這樣只需計(jì)算兩個(gè)數(shù)組的中位數(shù)是第幾個(gè)元素，代入功能函數(shù)即可。據(jù)此，根據(jù)二分法的性質(zhì)，我們?cè)谶f歸時(shí)可以將前即個(gè)元素排除。

Problem

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Example

Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Challenge

The overall run time complexity should be O(log (m+n)).

Note

由于要求O(log(m+n))的時(shí)間，所以選擇二分法。
思路是找到兩個(gè)數(shù)組合并起來(lái)的第k個(gè)元素。這樣,只需計(jì)算兩個(gè)數(shù)組的中位數(shù)是第幾個(gè)元素，代入功能函數(shù)即可。當(dāng)然，這里要先判斷總長(zhǎng)度的奇偶性，若為奇數(shù)，則取中間的元素；若為偶數(shù)，則計(jì)算中間兩個(gè)數(shù)的平均值。

有兩點(diǎn)需要注意：
在功能函數(shù)findKth()中，雖然是尋找第k個(gè)元素，但是對(duì)應(yīng)數(shù)組的順序是k-1，；
由于二分搜索需要不斷遞歸，所以極限情況是k為1的時(shí)候，此時(shí)要返回A和B中首元素較小的那個(gè)。

二分搜索第k個(gè)元素的原理：
首先，找到k個(gè)元素的中點(diǎn)mid，令mid = k/2-1；
假設(shè)數(shù)組A和B的長(zhǎng)度都大于首元素加上mid個(gè)元素的長(zhǎng)度，那么，對(duì)于我們的數(shù)組A的前mid個(gè)元素和數(shù)組B的前mid個(gè)元素，一定不包含要找的第k個(gè)元素。
據(jù)此，根據(jù)二分法的性質(zhì)，我們?cè)谶f歸時(shí)可以將前mid+1（即k/2）個(gè)元素排除。
那么，排除A還是B的前mid+1個(gè)元素呢？
比較一下A和B的第mid+1個(gè)元素，哪個(gè)小就排除該數(shù)組的前mid+1個(gè)元素。
然后，繼續(xù)遞歸查找第k-k/2個(gè)元素。

Solution

    class Solution {
        public double findMedianSortedArrays(int[] A, int[] B) {
            int len = A.length + B.length;
            if (len % 2 == 0) return (findKth(A, 0, B, 0, len/2)+findKth(A, 0, B, 0, len/2+1))/2.0;
            else return findKth(A, 0, B, 0, len/2+1);
        }
        public double findKth(int[] A, int Astart, int[] B, int Bstart, int k) {
            if (Astart == A.length) return B[Bstart+k-1];
            else if (Bstart == B.length) return A[Astart+k-1];
            if (k == 1) return Math.min(A[Astart], B[Bstart]);
            int mid = k/2-1, kNew = k-k/2, kA = Integer.MAX_VALUE, kB = kA;
            if (Astart + mid < A.length) kA = A[Astart+mid];
            if (Bstart + mid < B.length) kB = B[Bstart+mid];
            if (kA < kB) return findKth(A, Astart+k/2, B, Bstart, kNew);
            else return findKth(A, Astart, B, Bstart+k/2, kNew);
        }
    }

Naive method: O(m+n) time

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int len = n1+n2;
        if (len%2 == 0) return (find(nums1, nums2, len/2)+find(nums1, nums2, len/2+1))/2.0;
        else return (double)find(nums1, nums2, len/2+1);
    }
    public int find(int[] A, int[] B, int k) {
        int res = 0;
        int i = 0, j = 0;
        while (k != 0 && i < A.length && j < B.length) {
            if (A[i] < B[j]) res = A[i++];
            else res = B[j++];
            k--;
        }
        if (k != 0) {
            if (i < A.length) res = A[i+k-1];
            else res = B[j+k-1];
        }
        return res;
    }
}

Update 2018.8

//沒(méi)有使用二分法我覺(jué)得是一種退步
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;
        int[] nums = new int[totalLength];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] <= nums2[j]) {
                nums[k++] = nums1[i++];
            } else {
                nums[k++] = nums2[j++];
            }
        }
        while (i < nums1.length) {
            nums[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            nums[k++] = nums2[j++];
        }
        if (totalLength % 2 == 0) {
            return (double) (nums[totalLength/2-1] + nums[totalLength/2])/2;
        } else {
            return (double) nums[totalLength/2];
        }
    }
}