LeetCode 04：尋找兩個有序數組的中位數（Java實作）

• 題目

  給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。請你找出這兩個有序數組的中位數，并且要求算法的時間複雜度為 O(log(m + n))。你可以假設 nums1 和 nums2 不會同時為空。示例 1:nums1 = [1, 3]，nums2 = [2]，則中位數是 2.0示例 2:nums1 = [1, 2]，nums2 = [3, 4]，則中位數是 (2 + 3)/2 = 2.5來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/median-of-two-sorted-arrays著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

• 思路1：将兩個數組連接配接，排序，找中位數
• 代碼如下

public double findMediaSortedArrays(int[] nums1,int[] nums2){
  int l1 = nums1.length;
  int l2 = nums2.length;
  int[] nums = new int[l1+l2];
  
  if(l1==0){
   if(l2%2==0){
    return (nums2[l2/2-1]+nums2[l2/2])/2.0;
   }
   else return (nums2[l2/2]);  
  }
  if(l2==0){
   if(l1%2==0){
    return (nums1[l1/2-1]+nums1[l1/2])/2.0;
   }
   else return (nums1[l1/2]);  
  }
  
     int count = 0;
     int i = 0,j = 0;
     while(count<=l1+l2){
      if(nums1[i]<nums2[j]){
       nums[count++] = nums1[i++];
      }
      else nums[count++] = nums2[j++];
      
      if(i==l1){
       while(j!=l2){
       nums[count++] = nums2[j++];
       }
       break;
      }
      if(j==l2){
       while(i!=l1){
       nums[count++] = nums1[i++];
       }
       break;
      }
     }
     
     if(count%2==0){
     return (nums[count/2-1]+nums[count/2])/2.0;
     }
    else return (nums[count/2]); 
  }
 }
}
           

• 注意事項、細節

  1、當兩個數組内元素數量之和（count）為偶數時，應該"/2.0"而不是"/2"。

  2、涉及了數組就要防止“溢出”，這題中涉及了多處容易“溢出”的地方，應格外小心。

• 結果