1 寻找两正序数组中位数

分析

由于限制时间复杂度为 $O\log(m+n)$，因此可以联想到二分或者递归。
找中位数可转化为找第k大的值
选取两序列 $\lfloor k/2\rfloor-1$ 处的值进行比对，若A序列的小于B序列的则说明第k大的数不在A序列的左半边，可直接删去；若大于，则删除B左边的；若相等则A[$\lfloor k/2\rfloor-1$]或B[$\lfloor k/2\rfloor-1$]为第k大的数。
若处于3.中不相等的情况时，则应当转为寻找第k-$\lfloor k/2\rfloor$大的数。
若两数组中存在至少一个空集时，直接返回非空集的第k个元素。
若k=1，则返回A,B中第一个元素较大的。

\begin{algorithm} \caption{findK(nums1,m,nums2,n,x)} \begin{algorithmic} \If{m>n}\Comment{保证前一个传入的数组是个数较少的} \State \Return findK(nums2,n,nums1,x) \EndIf \If{m==0}\Comment{当存在空集合时另一个集合的第x个即为所求} \State \Return nums2[x-1] \EndIf \If{x==1}\Comment{当x为1时仅需比较两数组的首位即可} \State \Return min(nums1[0], nums2[0]) \EndIf \State ia = min($\lfloor x/2\rfloor$,m), ib = x - ia \Comment{保证比较前x个元素} \If{nums1[ia-1]<nums2[ib-1]} \State \Return findK(nums1[ia..], m-ia, nums2, n, x-ia) \Elif{nums1[ia-1]>nums2[ib-1]} \State \Return findK(nums1, m, nums2[ib..], n-ib, x-ib) \Else \State \Return nums1[ia-1] \EndIf \end{algorithmic} \end{algorithm}

\begin{algorithm} \caption{findMedian(nums1, nums2)} \begin{algorithmic} \State m=nums1.length,n=nums2.length \If{m+n为奇数} \State \Return findK(nums1, m, nums2, n, (m+n+1)/2) \Else \State \Return (findK(nums1, m, nums2, n, (m+n)/2)+findK(nums1, m, nums2, n, (m+n)/2+1))/2 \EndIf \end{algorithmic} \end{algorithm}

之所以此时的时间复杂度为 $O(\log(m+n))$ 是因为算法最多会运行 $\Theta(\log(x))$ ，而x的上界为m+n，因此时间复杂度为 $O(\log(m+n))$

from typing import List
class Solution:
    def findK(self, nums1: List[int], m: int, nums2: List[int], n: int, x: int) -> float:
        if m>n:
            return self.findK(nums2, n, nums1, m, x)
        if m==0:
            return nums2[x-1]
        if x==1:
            return min(nums1[0], nums2[0])
        ia = min(m, int(x/2)); ib = x - ia
        if nums1[ia-1] < nums2[ib-1]:
            return self.findK(nums1[ia:], m-ia, nums2, n, x-ia)
        elif nums1[ia-1] > nums2[ib-1]:
            return self.findK(nums1, m, nums2[ib:], n-ib, x-ib)
        else:
            return nums1[ia-1]
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1); n = len(nums2)
        if (m+n)%2 == 1:
            return self.findK(nums1, m, nums2, n, int((m+n+1)/2))
        else:
            return (self.findK(nums1, m, nums2, n, int((m+n)/2)) + self.findK(nums1, m, nums2, n, int((m+n)/2+1)))/2

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int total = m + n;
        if (total % 2 != 0) return findK(nums1.begin(), m, nums2.begin(), n, total / 2 + 1);
        else return (findK(nums1.begin(), m, nums2.begin(), n, total / 2) 
                    + findK(nums1.begin(), m, nums2.begin(), n, total / 2 + 1)) / 2.0;
    }
private:
    static int findK(vector<int>::const_iterator nums1, int m, vector<int>::const_iterator nums2, int n, int x){
        if (m > n) return findK(nums2, n, nums1, m, x);
        if (m == 0) return  *(nums2 + x - 1);
        if (x == 1) return min(nums1[0], nums2[0]);
        int ia = min(x/2, m), ib = x - ia; 
        if (*(nums1 + ia - 1) < *(nums2 + ib -1)) return findK(nums1 + ia, m - ia, nums2, n, x - ia);
        else if (*(nums1 + ia - 1) > *(nums2 + ib -1)) return findK(nums1, m, nums2 + ib, n - ib, x - ib);
        else return *(nums1 + ia -1);
    }
};