4. Median of Two Sorted Arrays

1.問題

• 找出兩list合併後的中位數

2.想法

• O(m + n): 比較兩list的元素並將最小值先放入list中, return list的中位數

• O(Log(m + n)):

  • k的初始值為(m + n) / 2, 每次都將k折半, 並比較nums1[k/2]與nums2[k/2], 如果nums1[k/2]較大, 則下次迭代時將不把比nums2[k/2]小的數字納入比較; 反之亦然

  • 此做法等於每次屑減 (m + n) /2, 再將剩下的(m + n) / 2個數字進行下一次迭代, 等同於使用Binary search

3.程式碼

• O(m + n)

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size1 = nums1.size();
        int size2 = nums2.size();
        
        int index1 = 0, index2 = 0;
        vector<int> v;
        while (index1 < size1 && index2 < size2)
        {
            if (nums1[index1] < nums2[index2])
            {
                v.push_back(nums1[index1]);
                index1++;
            }
            else if (nums1[index1] > nums2[index2])
            {
                v.push_back(nums2[index2]);
                index2++;
            }
            else
            {
                v.push_back(nums1[index1]);
                v.push_back(nums2[index2]);
                index1++;
                index2++;
            }
        }
        
        while (index1 < size1)
        {
            v.push_back(nums1[index1]);
            index1++;
        }
        
        while (index2 < size2)
        {
            v.push_back(nums2[index2]);
            index2++;
        }
        
        return ((size1 + size2) % 2 == 0) ? (double)(v[(size1 + size2 - 1)/2] + v[(size1 + size2 - 1)/2 + 1])/2 : v[(size1 + size2)/2];
    }
}

• O(Log(m + n))

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
		if (total & 0x1)
        {
            return findKth(nums1, 0, nums2, 0, total / 2 + 1);
        }
		else
			return (findKth(nums1, 0, nums2, 0, total / 2)
					+ findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2;
    }
private:
    double findKth(vector<int>& a, int idx1, vector<int>& b, int idx2, int k)
    {
        int m = a.size() - idx1; 
        int n = b.size() - idx2;
        if (m > n) {
		    return findKth(b, idx2, a, idx1, k);
        }
	    if (m == 0) {
		    return b[k - 1];
        }
	    if (k == 1) {
		    return min(a[idx1], b[idx2]);
        }
    
        //divide k into two parts
	    int pa = min(k / 2, m), pb = k - pa;
        if (a[idx1 + pa - 1] < b[idx2 + pb - 1]) {
            return findKth(a, idx1 + pa, b, idx2, k - pa);
        }
	    else if (a[idx1 + pa - 1] > b[idx2 + pb - 1]) {
            return findKth(a, idx1, b, idx2 + pb, k - pb);
        }
	    else {
		    return a[pa - 1];
        }
    }
};

4.References

• https://blog.csdn.net/yutianzuijin/article/details/11499917
• https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf