leetcode 4

两个已排序数组，超出所有这些数中第k大的元素。
只有最简单的暴力方法AC了……

思路：

1. 暴力合并然后排序 124 ms

class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: float
    """
    nums=nums1+nums2
    nums.sort()
    #奇数个
    if (len(nums1)+len(nums2))==1:
        return nums[0]
    elif((len(nums1)+len(nums2))%2==1):
        return nums[len(nums)/2]
    else:
        return (nums[len(nums)/2-1]+nums[len(nums)/2]) * 0.5

2. 双指针计数

排序这个过程太浪费了

边界条件没有考虑全：

class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: float
    """
    i,m,n=0
    while i<(len(nums1)+len(nums2))/2:
        if nums1[m]<nums2[n]:
            m++
            i++
            if i==(len(nums1)+len(nums2))/2:
                return nums1[m]
        else:
            n++
            i++
            if i==(len(nums1)+len(nums2))/2:
                return nums2[n]

3. 类似二分查找

https://leetcode.com/discuss/15790/share-my-o-log-min-m-n-solution-with-explanation
抓住问题本质，把问题转化成在一个列表中进行二分查找

def findMedianSortedArrays(self,A, B):
   m, n = len(A), len(B)
   #令前一个比较小
   if m > n:
       A, B, m, n = B, A, n, m
   if n == 0:
       raise ValueError

   imin, imax, half_len = 0, m, (m + n + 1) / 2
   while imin <= imax:
       i = (imin + imax) / 2
       j = half_len - i
       if j > 0 and i < m and B[j-1] > A[i]:
           # i is too small, must increase it
           imin = i + 1
       elif i > 0 and j < n and A[i-1] > B[j]:
           # i is too big, must decrease it
           imax = i - 1
       else:
           # i is perfect
           if i == 0: max_of_left = B[j-1]
           elif j == 0: max_of_left = A[i-1]
           else: max_of_left = max(A[i-1], B[j-1])

           if (m + n) % 2 == 1:
               return max_of_left

           if i == m: min_of_right = B[j]
           elif j == n: min_of_right = A[i]
           else: min_of_right = min(A[i], B[j])

           return (max_of_left + min_of_right) / 2.0