動機

這題體現了二分法是一種藝術

Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

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

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]Output: 2.00000Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]Output: 2.50000Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []Output: 2.00000

 

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

Sol

算中位數就是找中間的數，不然就是中間的兩個加起來除二， 但這裡我們沒辦法得到數字的座標，有沒有其他方法可以到中間?

用merge去數，數到一半就好， 但這要O(n+m)

能不能數快一點?

我們在merge時需要那些小數字嗎? 不用

我們能知道有沒有辦法確認這一區都是小數字? [1,2,3,4] 的話，i=2時能確認不論如何i<2的元素一定都比3小

如果兩條array都取同樣長度，像 [1,3,5]與[2,4,7]長度都2取會得到[1,3]與[2,4]

因為第一個array最後一個是3，所以裡面的元素都小於等於3，同理， 第二個array最後一個是4，所以裡面的元素都小於等於4

這樣我們可以知道有

  • 兩個小於3
  • 兩個小於4

而中位數一定在大的區間，所以可以把 兩個小於3 的區間當成已經merge的區間忽略不看

可以這樣如法炮製，就可以一直去掉最小的區間，最後只剩下一的話這就是我們要的數字。

這邊的思考方式是反覆挑一個array去出一半長度的array，因為每次都挑最小的，所以最後要的數字一定在某個array

用[0,3,5,7,9]與[2,2]當例子，求中位數

  • len:4 => 4//2 => {2, 2}
  • len:2 => 2//2 => {2, 2, 0}
  • len:1 => 3
def getN(n,i):
    if i >= len(n):
        return 999999
    else:
        return n[i]
def f(n1,n2,k):
    #print(n1,n2,k)
    if len(n1) == 0:
        return getN(n2, k-1)
    elif len(n2) == 0:
        return getN(n1, k-1)
    if k == 1:
        return min(getN(n1,k-1), getN(n2,k-1))
    else:
        a = getN(n1,k//2-1)
        b = getN(n2,k//2-1)
        #print(a,b,k-k//2)
        if a < b:
            #print('n1',n1[k//2:])
            return f(n1[k//2:],n2,k-k//2)
        else:
            #print('n2',n2[k//2:])
            return f(n1,n2[k//2:],k-k//2)
class Solution:
    def findMedianSortedArrays(self, n1: List[int], n2: List[int]) -> float:
        left = (len(n1)+len(n2)+1)//2
        right = (len(n1)+len(n2)+2)//2
        print(f(n1,n2,left), left)
        print(f(n1,n2,right), right)
        return (f(n1,n2,left)+f(n1,n2,right))/2.0