4. Median of Two Sorted Arrays

做题历程：

1. 2016/Oct/19,本题做过不止一次，这次仍然没有解出，大概耗时一小时+

本题有些难度，本来我思路是比较中点，然后同时删除小的左边和大的右边。。后来觉得太复杂了，虽然也通过了90%的case 后来，看了答案，觉得一道用寻找第k个元素的方法更好，说下大致的思路，细节还是得看代码：

1. 每次都删除最小的k / 2个元素
2. 具体是选每个array的第k / 2个元素，比较，然后把小的array的前k / 2个元素都删除。。。
3. 最后肯定会删成一个元素，此时取最小的

具体细节看代码，代码如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int l = (nums1.size() + nums2.size() + 1) / 2;
        int r = (nums1.size() + nums2.size() + 2) / 2;
//        cout << l << r << endl <<getKth(nums1, 0, nums2, 0, l) << getKth(nums1, 0, nums2, 0, r) << endl;
        return (getKth(nums1, 0, nums2, 0, l) + getKth(nums1, 0, nums2, 0, r)) / 2;
    }
private:
    double getKth(vector<int>& nums1, int l1, vector<int>& nums2, int l2, int k) {
        if (l1 + 1 > nums1.size()) {
            return nums2[l2 + k - 1];
        }
        if (l2 + 1 > nums2.size()) {
            return nums1[l1 + k - 1];
        }
        if (k == 1) {
            return min(nums1[l1], nums2[l2]);
        }

        int m1_elem = INT_MAX;
        int m2_elem = INT_MAX;
        if (l1 + k / 2 - 1 < nums1.size()) {
            m1_elem = nums1[l1 + k / 2 - 1];
        }
        if (l2 + k / 2 - 1 < nums2.size()) {
            m2_elem = nums2[l2 + k / 2 - 1];
        }
        if (m1_elem < m2_elem) {
            return getKth(nums1, l1 + k / 2, nums2, l2, k - k / 2);
        }
        else {
            return getKth(nums1, l1, nums2, l2 + k / 2, k - k / 2);
        }
    }
};