leetcode - 4. Median of Two Sorted Arrays @ Lung-Yu,Tsai 的部落格

題目：

There are two sorted arrays nums1 and 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)).

思路：

此題關鍵處是在於要在 O(log(m+n))的時間複雜度內完成.

而兩個排好序的數列若要重新組成並排序透過一般排序演算法必然超時.

但也由於輸入的兩個陣列本身皆以排序,因此僅須每個數值進行比較就可以在m+n的時間排序完成.

最後在直接取出中位數回傳即可完成。

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int size = nums1Size + nums2Size;
    int idx_median = size / 2;
    int *res_array = malloc(sizeof(int) * size);
    int i=0,j=0;
    double median_num = 0;
    
    while(i+j < size){
        if(i == nums1Size)
            res_array[(i+j)] = nums2[j++];
        else if(j == nums2Size)
            res_array[(i+j)] = nums1[i++];
        else if(nums1[i] < nums2[j])
            res_array[(i+j)] = nums1[i++];
        else
            res_array[(i+j)] = nums2[j++];
    }
    
    if(size % 2 == 0)
        median_num = ((double)res_array[idx_median] + (double)res_array[(idx_median-1)]) / 2;
    else
        median_num = res_array[idx_median];

    return median_num;
}