题目:

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

链接: 

题解：

仔细研究以后发现大家一般是两种解法

1. 把题目从find median转换为find k/2 th最小值。注意边界条件当k = 1时取A[0]与B[0]两数中较小者。Time Complexity O(log(m + n)，Space Complexity O(1)

public 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);            }        private double findKth(int A[], int A_start, int B[], int B_start, int k){        if(A_start >= A.length)            return B[B_start + k - 1];        if(B_start >= B.length)            return A[A_start + k - 1];        if(k == 1)            return Math.min(A[A_start], B[B_start]);        int A_key = A_start + k / 2 - 1 < A.length ? A[A_start + k / 2 - 1] : Integer.MAX_VALUE;        int B_key = B_start + k / 2 - 1 < B.length ? B[B_start + k / 2 - 1] : Integer.MAX_VALUE;        if(A_key < B_key)            return findKth(A, A_start + k / 2, B, B_start, k - k / 2);        else            return findKth(A, A_start, B, B_start + k / 2, k - k / 2);    }}

 

二刷:

Java:

Find Kth Smallest element

public class Solution {    public double findMedianSortedArrays(int[] nums1, int[] nums2) {        if (nums1 == null || nums2 == null) {            return 0.0;        }        int len = nums1.length + nums2.length;        if (len % 2 == 0) {            return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;        } else {            return findKth(nums1, 0, nums2, 0, len / 2 + 1);        }    }        private double findKth(int[] nums1, int nums1Start, int[] nums2, int nums2Start, int k) {        int nums1Len = nums1.length;        int nums2Len = nums2.length;        if (nums1Start >= nums1Len) {            return nums2[nums2Start + k - 1];        }        if (nums2Start >= nums2Len) {            return nums1[nums1Start + k - 1];        }        if (k == 1) {　　　　　　　　　　// for cases similar to nums1 = {5}, nums 2 = {3, 6}            return Math.min(nums1[nums1Start], nums2[nums2Start]);        }        int nums1Mid = nums1Start + k / 2 - 1 < nums1Len ? nums1[nums1Start + k / 2 - 1] : Integer.MAX_VALUE;        int nums2Mid = nums2Start + k / 2 - 1 < nums2Len ? nums2[nums2Start + k / 2 - 1] : Integer.MAX_VALUE;        if (nums1Mid < nums2Mid) {            return findKth(nums1, nums1Start + k / 2, nums2, nums2Start, k - k / 2);        } else {            return findKth(nums1, nums1Start, nums2, nums2Start + k / 2, k - k / 2);        }    }}

 

Python:

写法和naming convention都不太好，，只是ac而已，后面要refine

class Solution(object):    def findMedianSortedArrays(self, nums1, nums2):        """        :type nums1: List[int]        :type nums2: List[int]        :rtype: float        """        length = len(nums1) + len(nums2)        if length % 2 == 0:            return (self.findKth(nums1, 0, nums2, 0, length / 2) + self.findKth(nums1, 0, nums2, 0, length / 2 + 1)) / 2.0        else:            return self.findKth(nums1, 0, nums2, 0, length / 2 + 1)                    def findKth(self, nums1, nums1Start, nums2, nums2Start, k):        if nums1Start >= len(nums1):            return nums2[nums2Start + k - 1]        if nums2Start >= len(nums2):            return nums1[nums1Start + k - 1]        if k == 1:            return min(nums1[nums1Start], nums2[nums2Start])        nums1Mid = nums1[nums1Start + k / 2 - 1] if nums1Start + k / 2 - 1 < len(nums1) else sys.maxint        nums2Mid = nums2[nums2Start + k / 2 - 1] if nums2Start + k / 2 - 1 < len(nums2) else sys.maxint        if nums1Mid < nums2Mid:            return self.findKth(nums1, nums1Start + k / 2, nums2, nums2Start, k - k / 2)        else:            return self.findKth(nums1, nums1Start, nums2, nums2Start + k / 2, k - k / 2)

 

 

Binary Search， 这个速度非常快，在Erik Demaine的课件里有讲到解法。还可以使用Parallelism来继续进行优化，来达到O(n / lg²n)的时间复杂度。

Time Complexity - O(log(min(m, n)))， Space Complexity - O(1)

 

Reference: 

http://ocw.alfaisal.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf

http://www.cnblogs.com/springfor/p/3861890.html

http://blog.csdn.net/yutianzuijin/article/details/11499917

https://leetcode.com/discuss/17815/share-one-divide-conquer-log-method-with-clear-description

https://leetcode.com/discuss/11174/share-my-iterative-solution-with-o-log-min-n-m

https://leetcode.com/discuss/30807/o-lg-m-n-c-solution-using-kth-smallest-number

https://leetcode.com/discuss/20897/intuitive-python-solution-smallest-two-sorted-arrays-252ms

https://leetcode.com/discuss/67341/concise-java-solution-based-on-binary-search

https://leetcode.com/discuss/15790/share-my-o-log-min-m-n-solution-with-explanation

https://leetcode.com/discuss/41621/very-concise-iterative-solution-with-detailed-explanation

https://leetcode.com/discuss/9265/share-my-simple-o-log-m-n-solution-for-your-reference