4. Median of Two Sorted Arrays

[lancui1110]

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)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

[lancui1110]

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  var cat = nums1.concat(nums2), cen
  cat.sort(function (a, b) {
    return a-b
  })
  var catLen = cat.length
  if (catLen%2 !== 0) {
    cen = cat[(catLen-1)/2]
  } else {
    var cnum = catLen/2
    cen = ( cat[cnum-1] + cat[cnum] ) / 2
  }
  return cen
};

[KMBaby-zyl]

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let all = 0;

    nums1 = nums1.concat(nums2);
    nums1 = nums1.sort(function(a,b){return a - b});

    if(nums1.length % 2 === 1){
        return nums1[~~(nums1.length/2)]
    }else{
        return (nums1[nums1.length/2] + nums1[nums1.length/2 - 1])/2
    }

};

[evelynlab]

//思路：数组拼接，重新排序，取中位数（优化点：自己写排序方法，不用sort） var findMedianSortedArrays = function(nums1, nums2) { var arr = nums1.concat(nums2),res; arr.sort(function(a,b){ return a-b }) let len = arr.length; if (len%2 == 1){ res=arr[Math.floor(len/2)] } else{ res=(arr[len/2-1]+arr[len/2])/2 } return res };

[Ge-yuan-jun]

/**
 * 利用对比两个数组元素之间的大小直接排序
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */

var findMedianSortedArrays = function(nums1, nums2) {
    let [
      n, m, i, size, resultArr
    ] = [
      0, 0, 0, nums1.length + nums2.length, []
    ];
    let medianSize = Math.floor(size / 2);

    for (; i < size; i++) {
      if (nums1[m] === undefined && nums2[n] === undefined) {
        break;
      } else if (nums1[m] === undefined) {
        resultArr.push(nums2[n]);
        n ++;
      } else if (nums2[n] === undefined) {
        resultArr.push(nums1[m]);
        m ++;
      } else if (nums1[m] < nums2[n]) {
        resultArr.push(nums1[m]);
        m ++;
      } else {
        resultArr.push(nums2[n]);
        n ++;
      }

      if (resultArr.length > (medianSize + 1)) {
        break;
      }
    }

    return size % 2 === 1 ? 
          resultArr[medianSize] :
          ((resultArr[medianSize - 1] + resultArr[medianSize]) / 2);
};

[Ge-yuan-jun]

/**
 * 利用快排实现
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let arr = nums1.concat(nums2), res = 0;
    arr = quick_sort(arr);

    let len = arr.length, floor2 = Math.floor(arr.length/2);

    if (len % 2 === 1) {
      res = arr[floor2];
    } else {
      res = (arr[floor2 - 1] + arr[floor2]) / 2
    }

    return res
};

var quick_sort = function(arr) {

  let len = arr.length;
  let left = [], right = [];
  let mid = [arr[0]];

  if (len <= 1) {
    return arr;
  } else {
    let  i = 1;
    for (; i< len; i++) {
      if (arr[i] < mid[0]) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
  }

  return quick_sort(left).concat(mid.concat(quick_sort(right)));
}