LeetCode 4. Median of Two Sorted Arrays ( C )-Hard

Posted On 2021 年 4 月 24 日

題目為給定兩個已排序之整數陣列，請撰寫程式回傳兩陣列的中位數，如中位數有兩個則回傳兩者之平均值。

題目與範例如下

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

 

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.
Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000
Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000
 

Constraints:

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

Follow up: The overall run time complexity should be O(log (m+n)).

我的策略為先計算中間值為兩個整數或一個整數，並計算第一個中位數的位置。透過迴圈依序取出兩個整數陣列中最小的值，當該值為中位數時，如中位數為兩整數則儲存於temp中，並於下次回圈中回傳平均值，如中位數僅為單一數值則直接回傳。

下面是我的程式碼

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int yn = (nums1Size + nums2Size) % 2;
    short int middle = (nums1Size + nums2Size + 1)/2 -1;
    short int listptr1 = 0,listptr2 = 0, counter = 0;
    short int flag;                                  // 1 = next num at nums1, 2 = next num at nums1
    
    int tempnum = 0;
    
    while(listptr1<nums1Size || listptr2<nums2Size){
        
        if(listptr1 == nums1Size){
            flag = 2;
        }
        else if(listptr2 == nums2Size){
            flag = 1;
        }
        else{
            if(nums1[listptr1] > nums2[listptr2]){
                flag = 2;
            }
            else{
                flag = 1;
            }
        }
                
        if(counter == middle + 1){
            switch(flag){
                case 1 :
                    return (double) (nums1[listptr1] + tempnum)/2;
                case 2 :
                    return (double) (nums2[listptr2] + tempnum)/2;
            }
        }
        else if(counter == middle){
            switch(yn){
                case 0 :
                    switch(flag){
                        case 1 :
                            tempnum = nums1[listptr1];
                            listptr1 ++;
                            counter ++;
                            break;
                        case 2 :
                            tempnum = nums2[listptr2];
                            listptr2 ++;
                            counter ++;
                            break;
                    }
                    break;
                case 1 :
                    switch(flag){
                        case 1 :
                            return (double) nums1[listptr1];
                        case 2 :
                            return (double) nums2[listptr2];
                    }
            }
        }
        else{
            switch(flag){
                case 1 :
                    listptr1 ++;
                    counter ++;
                    break;
                case 2 :
                    listptr2 ++;
                    counter ++;
                    break;
                    
            }            
        }
    }
    return 0;
}

yn 為判斷幾個中位數，1為一個中位數，2為兩個中位數。

middle 為判斷地一個中位數的位址 ( index ) ，listptr1 用來遍歷 nums1 整數陣列，listptr2 用來遍歷 nums2 整數陣列。

counter 用來判別已遍歷的數量。

flag 判別此輪要取出之數字為 nums1 陣列中的 ，或是 nums2 陣列中的，1 為 nums1，2 為 nums2。

下面是時間與空間之消耗

Runtime: 4 ms, faster than 99.89% of C online submissions for Median of Two Sorted Arrays.

Memory Usage: 6.4 MB, less than 74.69% of C online submissions for Median of Two Sorted Arrays.

此次執行測試的次數比較多，進而發現同一份程式碼每次執行的時間與空間消耗其實都不相同，所以僅能當參考使用。

下一題連結 : LeetCode 5. Longest Palindromic Substring ( C )-Medium