2020-04-06

针对第四题，一看到 O(logN) ,只有二分了。为了减少代码行数，才未遵守规范。

先写O(m+n),,对数组总长度 ，奇偶 奇偶奇偶奇偶 奇偶，要分开算的。
python 3

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        i=nums1+nums2
        i.sort()
        s=len(i)
        t=s//2
        if s%2 == 1:return i[t]
        else:return 0.5*(i[t]+i[t-1])

Tim 排序太复杂了。自己归并吧

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        i,j,a,x,y=nums1,nums2,[],0,0
        m,n=len(i),len(j)
        while x<m and y<n:
            if i[x]<=j[y]:
                a.append(i[x]);x+=1
            else:
                a.append(j[y]);y+=1
        if x<m:
            a+=i[x:]
        if y<n:
            a+=j[y:]
        t=(m+n)//2
        if (m+n)%2 == 1:return a[t]
        else:return 0.5*(a[t]+a[t-1])

执行时间56ms，比不上它。
下面实现二分法。这道题，对于数组下标的处理，考察到位了

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        i,j=nums1,nums2
        m,n=len(i),len(j)
        z=m+n
        k=z//2
        #a,b =array ;s,s2=start ;e,e2=end ,w is k
        def f(a,s,e,b,s2,e2,w):
            x,y=e-s+1,e2-s2+1
            #the short one move to first 
            if x>y:return f(b,s2,e2,a,s,e,w)  
             #only one is left
            if x==0:return b[s2+w-1]  

            if w==1:return min(a[s],b[s2])
            #find the total w =w//2+w//2
            #这里是难点，如果每次都是w//2 ,那便于理解
            #当w是奇数时，c会多取一位，比如w==5，x较大时，d=2，c=3
            d=min(w//2,x)
            c= w-d  # the most useful line

            p=a[s+d-1]
            q=b[s2+c-1]
            if p==q:return p
            #这里可以肯定b的前一部分中一定没有中位数了，砍去。
            #a的后面部分，同理，砍去。
            #b砍去的部分，一定排在合并虚拟排序后的前面，所以，找第w小的数，变为w-c 
            elif p>q:return f(a,s,s+d-1,b,s2+c,e2,w-c)
            else:return f(a,s+d,e,b,s2,s2+c-1,w-d)

        m-=1;n-=1
        if z%2==1:return 1.0*f(i,0,m,j,0,n,k+1)
        else: return 0.5*(f(i,0,m,j,0,n,k+1)+f(i,0,m,j,0,n,k))

1.中位数对整除运算的理解，加深了，if w==1:return min(a[s],b[s2])
2.在递归中，w 一直在变小，或者其中一个数组为0
3、切片操作，要小心，数组下标从0开始，牢记。
4、对比随机选择算法，w一直变化
5、f函数，发现第w小的数，不是下标，是数组的值。
6、证明 if x==0:return b[s2+w-1]
x最小值为0，不可能为负数
因为s+d ，d最大为x，x为当前数组的长度。当d==x，s+x=e+1
因为x=e-s+1（在本轮中）
所以，针对下一轮，x=e-s+1=e-(e+1)+1=0, 证明了x的最小值。
牺牲可读性，提高性能，优化的基础是理解上面的。

class Solution:
    def findMedianSortedArrays(self, i, j):
        m,n=len(i),len(j)
        z=m+n
        k=z//2 +1
        def f(a,s,e,b,s2,e2,w):
            x,y=e-s,e2-s2  #change 1
            if x>y :return f(b,s2,e2,a,s,e,w)
            if x<0 :return b[s2+w-1] #change 2
            if w==1:return min(a[s],b[s2])
            d=min(w//2,x+1) #change 3
            c=w-d 
            v=a[s+d-1]
            u=b[s2+c-1]
            if v==u:return u
            elif v>u:return f(a,s,s+d-1,b,s2+c,e2,w-c)
            else:return f(a,s+d,e,b,s2,s2+c-1,w-d)
        m-=1;n-=1
        t=f(i,0,m,j,0,n,k)
        if z%2==1:return t
        else:
            return 0.5*(t + f(i,0,m,j,0,n,k-1))