LeetCode#4 Median of Two Sorted

There are two sorted arrays nums1 and nums2 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)).

Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
题目还是很好理解的，有两个有序列表，求他们合在一起之后的中位数，偶数个取中间两个的平均值。
讲道理一个一个比较一下就可以出来，但是时间要求是log，需要一点算法的加工。照样是看答案，126sm。

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        #A短B长,m小n大
        n,m,B,A=len(nums1),len(nums2),nums1,nums2
        if len(nums1)<len(nums2) :
            n,m,B,A=len(nums2),len(nums1),nums2,nums1
        if n==0:
            raise ValueError
#这里是在处理输入：[],[1]这种的时候，下面的代码会报错，所以直接输出n的中位数
        if m==0:
            return B[n/2] if n%2==1 else (B[n/2-1]+B[n/2])/2.
        #half对奇数上取整
        imin,imax=0,m
        #m短，遍历一遍短的
        while(imin<=imax):
            i=(imin+imax)/2
            j=(m+n+1)/2-i
            if i>0 and A[i-1]>B[j]:
                #A[i-1]大了证明i的位置在i-1之前，不可能在i-1之后
                imax=i-1
            elif i<m and B[j-1]>A[i]:
                #A[i]小了，证明i的位置在i之后，不可能在i之前
                imin=i+1
            else:
                #ij到左边界了
                if (i==0): left = B[j-1]
                elif (j==0): left = A[i-1]
                #ij找到最佳位置
                else: left=max(A[i-1],B[j-1])
                #ij到右边界了
                if (i==m): right = B[j]
                elif (j==n): right = A[i]
                #ij找到最佳位置
                else: right = min(A[i],B[j])
                if (m+n)%2 == 1:
                    return left
                return (left+right)/2.0

再附上一个大神ChuntaoLu 写的利用第k小求解的代码

#这个函数用来确定AB合并后list的中间值
def findMedianSortedArrays(self, A, B):
    l = len(A) + len(B)
    if l % 2 == 1:
#利用第k小求解，k设为中间值下标
        return self.kth(A, B, l // 2)
    else:
        return (self.kth(A, B, l // 2) + self.kth(A, B, l // 2 - 1)) / 2.   
#递归求解第k小 
def kth(self, a, b, k):
    if not a:
        return b[k]
    if not b:
        return a[k]
#有点像是二分查找，从中间开始，如果中间值<k，证明k在右边，否则k在左边，降低复杂度
    ia, ib = len(a) // 2 , len(b) // 2
    ma, mb = a[ia], b[ib]
   #k在ia,ib右边
    if ia + ib < k:
#mb 小，让mb变大
        if ma > mb:
            return self.kth(a, b[ib + 1:], k - ib - 1)
        else:
            return self.kth(a[ia + 1:], b, k - ia - 1)
＃k在ia,ib左边
    else:
#ma大，ma变小
        if ma > mb:
            return self.kth(a[:ia], b, k)
        else:
            return self.kth(a, b[:ib], k)

中间有个符号//，之前没用过，百度之后是这么说的：

from __future__ import division
#一看到这句，" / "就表示 浮点数除法，返回浮点结果;" // "表示整数除法。
#但是，预计在Python3.0发布时，就没有这种折中情况了，，" / "就一定表示 浮点数除法，返回浮点结果;" // "表示整数除法。

还有奇偶数判断，看到了这样的写法：

x&1
#和x%2的效果是一样的，这个是为运算