Problem

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]
  2. Output: 2.00000
  3. Explanation: merged array = [1,2,3] and median is 2.
  1. Input: nums1 = [1,2], nums2 = [3,4]
  2. Output: 2.50000
  3. Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
  1. Input: nums1 = [0,0], nums2 = [0,0]
  2. Output: 0.00000
  1. Input: nums1 = [], nums2 = [1]
  2. Output: 1.00000

Solution

  1. var findMedianSortedArrays = function (nums1, nums2) {
  2.     var len = nums1.length + nums2.length;
  3.     var midIndex1 = Math.floor(len / 2);
  4.     var midIndex2 = midIndex1;
  5.     if (len % 2 === 0) {
  6.         midIndex2 = midIndex1 - 1;
  7.     }
  9.     if (nums1.length === 0) {
  10.         return (nums2[midIndex1] + nums2[midIndex2]) / 2;        
  11.     }
  12.     if (nums2.length === 0) {
  13.         return (nums1[midIndex1] + nums1[midIndex2]) / 2;        
  14.     }
  16.     var arr = [];
  17.     var source1 = [...nums1], source2 = [...nums2];
  19.     while(arr.length <= midIndex1) {
  20.         if (source1.length === 0) {
  21.             let index1 = midIndex1 - arr.length;
  22.             let index2 = (index1 - (midIndex1 - midIndex2));
  23.             let num1 = source2[index1];
  24.             let num2 = index2 >= 0 ? source2[index2] : arr[arr.length - 1];
  25.             return (num1 + num2) / 2;
  26.         }
  27.         if (source2.length === 0) {
  28.             let index1 = midIndex1 - arr.length;
  29.             let index2 = (index1 - (midIndex1 - midIndex2));
  30.             let num1 = source1[index1];
  31.             let num2 = index2 >= 0 ? source1[index2] : arr[arr.length - 1];
  32.             return (num1 + num2) / 2;
  33.         }
  35.         if (source1[0] < source2[0]) {
  36.             arr.push(...source1.splice(0, 1));
  37.         } else {
  38.             arr.push(...source2.splice(0, 1));
  39.         }
  40.     }
  42.     return (arr[arr.length - 1] + arr[arr.length - 1 - (midIndex1 - midIndex2)]) / 2;
  43. };