yoruru的努力日記

4. Median of Two Sorted Arrays

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.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

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

Constraints:

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

SOL：

這一題真的超難！！參考了很多講解後，我最後還是看花花的影片才看懂的，圖解相對而言清楚很多。(但還是看超多次

花花酱 LeetCode 4. Median of Two Sorted Arrays - 刷题找工作 EP102

解題思想如下：若兩個array的總和是偶數，則將這兩個array排序後，會有前k個元素，以及後k個元素，元素Cₖ則是前k個元素的下一個，若兩個array的總和是奇數，則將這兩個array排序後，會有前k個元素，以及後k個元素，元素Cₖ則在這兩個個數相等的array中間。

在這兩個sorted array中，我們透過m1+m2=k來找出k在哪裡。比較nums1[m1]跟nums2[m2-1]來調整l跟r，以求能找到正確的m1。若nums1[m1]較小，則應該往後找，所以l=m1+1；否則nums1[m1]太大。必須往前找r=m1。

希望幫助大家更好理解：這個解法裡面我們要binary search 查找的變量m1，其實是“在較短數組取m1個數，放在中位數左邊”。所以開頭確保n1 <= n2的步驟除了比較快，也是保證while loop裡面查找步驟不會越界，因為左右中位數一定不會同時出現在較小的數組。while loop裡面0<= m1 <= n1 -1, 1<= m2 <= k < n2。只要m1確定了中位數也可以確定了。因為取m1個數在中位數左邊，那麼nums1[m1]代表的是中位數/左中位數，當從nums2取m2個數放在中位數左邊時，最大的數nums2[m2-1]須小於nums1[m1]。

#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){

    if(nums1Size>nums2Size)
        return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
    
    int k = (nums1Size + nums2Size + 1) / 2;
    int l = 0;
    int r = nums1Size;
    int m1 = 0;
    int m2 = 0;
    while(l<r){
        m1 = l + (r-l)/2;
        m2 = k - m1;
        if(nums1[m1]<nums2[m2-1])
            l = m1+1;
        else
            r = m1;
    }

    m1 = l;
    m2 = k-l;
    int c1 = MAX((m1<=0?INT_MIN:nums1[m1-1]),(m2<=0?INT_MIN:nums2[m2-1]));
    int c2 = MIN((m1>=nums1Size?INT_MAX:nums1[m1]),(m2>=nums2Size?INT_MAX:nums2[m2]));
    
    if((nums1Size + nums2Size)%2==1)
        return c1;
    else
        return (c1+c2)*0.5;
}