LeetCode从零刷起 (4. Median of Two S

这道题是我刷leetcode遇到的第一个难度为Hard的题，笔者在大学学习算法课的时候接触过类似的题目，不过由于时间久了，加之当时并没有对这类题型有一个深刻的理解，所以忘了做法了。在查阅了一些技术类博客之后，才找回了当时的思路。

题目叙述如下：

There are two sorted arrays nums1and 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

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

题目简介

这道题的输入是两个已经sorted的数组，要求返回两数组合并后的中位数，时间复杂度要求为O(log (m+n))

知识要点

1. 本题若不考虑时间复杂度的要求，我们很容易想到mergeSort。将两个排序好的数组合并成一个数组称为一次merge。做法很简单：设置两个指向两数组的头指针，每次取更小的元素往新数组里添加，并向后移动该指针，直到两个数组的数都被取出。（本题用这种思想不符合时间复杂度要求）
2. 二分查找的思想，能够使时间复杂度降至O(log (m+n))

解题思路

Approach 1: MergeSort

应用mergeSort中一次merge，从而找到我们要的中位数。此方法很简单，在此不列代码。但是此方法不符合O(log (m+n))时间复杂度的要求

Approach 2: Binary Discard

Binary Discard 是笔者自己起的名字，参考 Leetcode 4 Median of Two Sorted Arrays 原文的解释是英文，在这里我简单翻译一下：

在这里问题泛化为：寻找两个sorted数组的第k小的元素。
如果我们比较一下A里第k/2个和B里第k/2个元素（即比较A[k/2-1]和B[k/2-1]）的话，存在三种情况：（这里我们比较理想地认为k为偶数，且两个数组的元素个数都大于等于k/2。事实证明非理想情况下，通过下文中的细节处理，结果相同）
A[k/2-1] = B[k/2-1]
A[k/2-1] < B[k/2-1]
A[k/2-1] > B[k/2-1]
第一种情况：我们已经找到了目标值，正好就是A[k/2-1]或B[k/2-1]。我们可以用一个表格来清晰的表示，A和B mergeSort之后的数组的情况如下：

1th : (k-2)th	(k-1)th	kth	(k+1)th : last
A[0:k/2-2] and B[0:k/2-2]	A[k/2-1]	B[k/2-1]	A[k/2:last] and B[k/2:last]

第二种情况：A[0:k/2-1]中的所有元素，都在AB合并数组里的前k个最小元素里。换句话说：A[k/2-1]小于AB合并数组的第k小的元素。这一点我们可以通过反证法来证明，还是很好理解的，在这里就不证明了。所以我们可以丢弃A[0:k/2-1]中的所有元素。
**第三种情况： **与情况二同理

接下来我们考虑一下edge condition，即递归函数的终止条件。

1. 当A或B其中一个数组为空时，返回A[k-1] (或B[k-1])
2. 当k = 1时(且A,B均不空)，返回min(A[0], B[0])
3. 当A[k/2-1] = B[k/2-1]时，返回其中一个即可

剩下的就是一些细节处理了。

1. 为了操作方便，我们令m总是小于n
2. 我们用<code>pa = min(k/2, m);</code>来表示A中选取元素的数量；用<code>pb = k - pa;</code>表示B中选取元素的数量。这样的话一些特殊情况（比如当m < k/2时，或者k为奇数时）也同样能够得到正确结果。
3. 若A,B元素个数和 m+n 为奇数，中位数为寻找第 (m+n)/2+1 最小的数；
   若A,B元素个数和 m+n 为偶数，中位数为寻找第 (m+n)/2 和第 (m+n)/2+1 最小的数的平均数

具体的C++代码如下：

class Solution {
public:
    int min(int a, int b){
        return a<b? a:b;
    }
    
    int findKth(int k, vector<int> nums1, vector<int> nums2){
        int m = nums1.size(), n = nums2.size();
        //assume m <= n;
        if (m > n)
            return findKth(k, nums2, nums1);
            
        //2 terminate conditions
        if (m == 0)
            return nums2[k-1];
        if (k == 1)
            return min(nums1[0], nums2[0]);
        
        //two parts and discard one
        int pa = min(k/2, m);
        int pb = k - pa;
        if (nums1[pa-1] > nums2[pb-1]){
            nums2.erase(nums2.begin(), nums2.begin()+pb);
            return findKth(k-pb, nums1, nums2);   
        }
        else if (nums1[pa-1] < nums2[pb-1]){
            nums1.erase(nums1.begin(), nums1.begin()+pa);
            return findKth(k-pa, nums1, nums2);
        }
        else
            return nums1[pa-1];
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int cnt = nums1.size() + nums2.size();
        if (cnt % 2 == 1)
            return (double)findKth(cnt/2+1, nums1, nums2);
        else
            return (findKth(cnt/2, nums1, nums2) + findKth(cnt/2+1, nums1, nums2)) / 2.0;
    }
};