Median of Two Sorted Arrays 的 ja

分析

首先想到的方法应该是将两个数组 nums1 和 nums2 合并成一个新的数组 arr，在合并的过程中需要确保该新数组有序，这时候再根据新数组中包含数字的个数来求最后的结果：

• 若包含数字个数是奇数，直接取数组的中间值作为最后的结果
• 若包含数字个数是偶数，取数组最中间的两个数字的均值作为最后的结果

显然，生成新的数组需要遍历两个数组，但是其实并不需要完整的遍历两个数组，只需要计算遍历的次数是两个数组长度的均值即可，这个时候就能发现中间的值了。

解答

代码如下：

var findMedianSortedArrays = function(nums1, nums2) {
  if ( !(Array.isArray(nums1) && Array.isArray(nums2)) || (nums1.length === 0 && nums2.length === 0) ) return;

  var arr = [],
      mlen = nums1.length,
      nlen = nums2.length,
      isOdd = ( nums1.length + nums2.length )%2;

  // nums1 和 nums2 中有一个是空数组，就计算并返回另一个数组的中间值
  if ( mlen === 0 ) return nlen%2 ? nums2[ Math.floor(nlen/2) ] : ( nums2[nlen/2 - 1] + nums2[nlen/2] )/2;
  if ( nlen === 0 ) return mlen%2 ? nums1[ Math.floor(mlen/2) ] : ( nums1[mlen/2 - 1] + nums1[mlen/2] )/2;

  // 遍历的次数为两个数组长度的均值
  while ( arr.length !== Math.floor((mlen + nlen)/2) ){
    // 1. 若遍历的过程中两个数组中有一个空了，则弹出另一个的首值并压入 arr 中
    // 2. 两个数组都没有空的话，比较他们首值的大小，将较小的弹出并压入 arr 中
    if ( nums2[0] === undefined || nums1[0] <= nums2[0] ){
      arr.push( nums1.shift() );
    } else {
      arr.push( nums2.shift() );
    }
  }

  // 遍历结束后两个数组中有一方变成空数组的情况
  // 奇数，那么剩下的非空数组的首值就是最后的结果
  // 偶数，那么剩下的非空数组额首值与 arr 的末值的均值就是最后的结果
  if ( nums1[0] === undefined ) return isOdd ? nums2[0] : (nums2[0] + arr[arr.length - 1])/2;
  if ( nums2[0] === undefined ) return isOdd ? nums1[0] : (nums1[0] + arr[arr.length - 1])/2;

  // 遍历结束后两个数组均非空的情况
  // 奇数，两个数组首值的较小值就是最后的结果
  // 偶数，两个数组首值的较小值与 arr 末值的均值就是最后的结果
  if ( isOdd ){
    return nums1[0] < nums2[0] ? nums1[0] : nums2[0];
  } else {
    return nums1[0] < nums2[0] ? (nums1[0] + arr[arr.length-1])/2 : (nums2[0] + arr[arr.length - 1])/2;
  }
};