第 93 题：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log(m+n))。

[yygmind]

示例 1：

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

中位数是 2.0

示例 2：

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

中位数是(2 + 3) / 2 = 2.5

[AEPKILL]

想到一个 O(n) 的解法，类似归并排序，抛砖引玉

const findMedianSortedArrays = function(
    nums1: number[],
    nums2: number[]
  ) {
    const lenN1 = nums1.length;
    const lenN2 = nums2.length;
    const median = Math.ceil((lenN1 + lenN2 + 1) / 2);
    const isOddLen = (lenN1 + lenN2) % 2 === 0;
    const result = new Array<number>(median);

    let i = 0; // pointer for nums1
    let j = 0; // pointer for nums2

    for (let k = 0; k < median; k++) {
      if (i < lenN1 && j < lenN2) {
        // tslint:disable-next-line:prefer-conditional-expression
        if (nums1[i] < nums2[j]) {
          result[i + j] = nums1[i++];
        } else {
          result[i + j] = nums2[j++];
        }
      } else if (i < lenN1) {
        result[i + j] = nums1[i++];
      } else if (j < lenN2) {
        result[i + j] = nums2[j++];
      }
    }

    if (isOddLen) {
      return (result[median - 1] + result[median - 2]) / 2;
    } else {
      return result[median - 1];
    }
  };

[Molunerfinn]

加了注释，好理解一点，时间复杂度O(log(n+m))：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  let m = nums1.length
  let n = nums2.length
  let k1 = Math.floor((m + n + 1) / 2)
  let k2 = Math.floor((m + n + 2) / 2)

  return (findMedianSortedArraysCore(nums1, 0, nums2, 0, k1) + findMedianSortedArraysCore(nums1, 0, nums2, 0, k2)) / 2
};

/**
 * 
 * @param {number[]} nums1 
 * @param {number[]} nums2 
 * @param {number} i 
 * @param {number} j 
 * @param {number} k 
 * @return {number}
 */
const findMedianSortedArraysCore = (nums1, i, nums2, j, k)  => {
  // 如果数组起始位置已经大于数组长度-1
  // 说明已经是个空数组
  // 直接从另外一个数组里取第k个数即可
  if (i > nums1.length - 1) {
    return nums2[j + k - 1]
  }
  if (j > nums2.length - 1) {
    return nums1[i + k - 1]
  }
  // 如果k为1
  // 就是取两个数组的起始值里的最小值
  if (k === 1) {
    return Math.min(nums1[i], nums2[j])
  }
  // 取k2为(k/2)或者数组1的长度或者数组2的长度的最小值
  // 这一步可以避免k2大于某个数组的长度（长度为从起始坐标到结尾）
  let k2 = Math.floor(k / 2)
  let length1 = nums1.length - i
  let length2 = nums2.length - j
  k2 = Math.min(k2, length1, length2)

  let value1 = nums1[i + k2 - 1]
  let value2 = nums2[j + k2 - 1]

  // 比较两个数组的起始坐标的值
  // 如果value1小于value2
  // 就舍弃nums1前i + k2部分
  // 否则舍弃nums2前j + k2部分
  if (value1 < value2) {
    return findMedianSortedArraysCore(nums1, i + k2, nums2, j, k - k2)
  } else {
    return findMedianSortedArraysCore(nums1, i, nums2, j + k2, k - k2)
  }
}

[xiongchenf]

leetcode提交，算法耗时190ms

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let num = nums1.concat(nums2);
    num = num.sort((a, b) => a - b);
    let mid = Math.floor(num.length / 2);
    if (num.length % 2 === 0) {
        return (num[mid-1] + num[mid])/2
    } else {
        return num[mid]
    }
};

[Molunerfinn]

@xiongchenf 兄弟，你用了sort之后时间复杂度已经是O(nlog(n))了，不符合题目O(log(m+n))

[yelin1994]

function getMidPointNumber (arr1, arr2) {
   const result = []
   const len1 = arr1.length
   const len2 = arr2.length
   let i = 0
   let j = 0
   let count = 0
   while (true) {
       if (i == len1 && j == len2)  {
           break
       }
       if (i < len1 && j < len2 && arr1[i] <= arr2[j]) {
           result.push(arr1[i])
           i++
       } else if (i < len1 && j < len2 && arr2[j] < arr1[i]) {
           result.push(arr2[j])
           j++
       } else if (i === len1 && j < len2) {
           while (j < len2) {
               result.push(arr2[j])
               j++
           }
       } else if (j === len2 && i < len1) {
           while (i < len1) {
               result.push(arr1[i])
               i++
           }
       }
   }
   const mid = (len1 + len2) / 2
   if ((len1 + len2) % 2 === 1 ) {
       return result[mid]
   } else {
       return ((result[mid] + result[mid + 1]) / 2)
   }
}

[kungithub]

function mid(arr1, arr2) {

    function findIndex(kArray) {
        let value;
        let tmp = 0;
        let k = kArray[tmp];
        let result = [];
        function find(arr, i, j) {
            if (i < j) {
                let left = i;
                let right = j;
                let pivot = arr[left];
                while (i < j) {
                    while (arr[j] < pivot && i < j) j--
                    // 交换位置
                    if (i < j) arr[i++] = arr[j];
                    while (arr[i] > pivot && i < j) i++;
                    if (i < j) arr[j--] = arr[i];
                }
                arr[i] = pivot;
                if (i === k) {
                    value = arr[i];
                }
                if (i - 1 == left && i > k) {
                    value = arr[left];
                }
                if (i + 1 == right && i < k) {
                    value = arr[right];
                }
                
                // 找到第一位之后，再找下一位，只需要在当前位置之后查找，不用重新循环数组
                // 因为我的入参是从小到大的
                if (value) {
                    result.push(value);
                    value = undefined;
                    if (tmp == kArray.length - 1) return;
                    k = kArray[++tmp];
                    if (i == k) {
                        result.push(arr[i]);
                        return;
                    }
                    if (right == k) {
                        result.push(arr[right]);
                        return;
                    }
                }
                // 从左边找
                if (i > k) find(arr, left, i - 1);
                // 从右边找
                if (i < k) find(arr, i + 1, right);
            }
        }

        find(arr, 0, arr.length - 1);
        return result;
    }

    var arr = arr1.concat(arr2);
    var k = [];
    if (arr.length % 2 == 0) k = [arr.length / 2 - 1, arr.length / 2];
    else k = [Math.floor(arr.length / 2)];
    var d = findIndex(k);
    return d.length == 1 ? d[0] : (d[0] + d[1]) / 2;
}

思路是分治查找，利用类似TopK的思路，连续找两个指定的数，复杂度是O( log(m+n))
首先concat数组，然后判断数组长度是奇数偶数
奇数直接找第n/2位
偶数找n/2-1,n/2位 除2

[huangche007]

@Molunerfinn 老哥，厉害了！

[5SSS]

function findMiddleNumber (nums1, nums2) {
    let length = nums1.length + nums2.length
    let index_1 = 0
    let index_2 = 0
    let merge = []

    while (length >= 0) {
      if (index_1 >= nums1.length || index_2 >= nums2.length) {
        break
      }
      if (nums1[index_1] < nums2[index_2]) {
        merge.push(nums1[index_1])
        index_1++
      } else {
        merge.push(nums2[index_2])
        index_2++
      }
      length--
    }

    if (index_1 < nums1.length) {
      merge = merge.concat(nums1.splice(index_1))
    } else {
      merge = merge.concat(nums2.splice(index_2))
    }

    let middleIndex = Math.floor(merge.length / 2)
    if (merge.length % 2 === 0) {
      return (merge[middleIndex] + merge[middleIndex - 1]) / 2
    }
    return merge[middleIndex]
  }

提交结果	执行用时
通过	152 ms

[JILL1231]

@xiongchenf 兄弟，你用了sort之后时间复杂度已经是O(nlog(n))了，不符合题目O(log(m+n))

大神是如何验证时间复杂度为 O(log(m+n)) ？？？

[wjkang]

看下大O复杂度计算方法，哪来的O(log(m+n))

[tgxhx]

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  var nums = []
  while (nums1.length && nums2.length) {
    if (nums1[0] < nums2[0]) {
      nums.push(nums1.shift())
    } else {
      nums.push(nums2.shift())
    }
  }
  nums = nums.concat(nums1, nums2)
  var median
  if (nums.length % 2) {
    median = nums[Math.floor(nums.length / 2)]
  } else {
    var m = nums.length / 2
    median = (nums[m - 1] + nums[m]) / 2
  }
  return median
}

Runtime: 108 ms

[zhengjianghao]

这个在leetCode上有， 不考虑时间负责度的情况下 把两个数组合并 -> 排序 -> 单数取中间，双数取中间两个平均值

[yanheSu]

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let len1 = nums1.length;
    let len2 = nums2.length;
    let len = len1 + len2;
    if(len === 0){
        throw 'lalalal';
    }
    let lastNum = 0;
    let targetLenIsOdd = isOdd(len);
    let targetIndexEntry =  targetLenIsOdd ? len / 2 | 0 : len / 2 - 1;
    let result = [];
    for(let i = 0,j = 0,s = 0; i < len1 || j < len2;){
        if(i !== len1 && j !== len2){
            if(nums1[i] < nums2[j]){
                lastNum = nums1[i];
                i++;
            } else {
                lastNum = nums2[j];
                j++;
            }
        } else if(i !== len1){
            lastNum = nums1[i];
            i++;
        } else {
            lastNum = nums2[j];
            j++;
        }

        if(targetIndexEntry <= s){
            result.push(lastNum);
            if(targetLenIsOdd){
                result = result[0];
                break;
            } else {
                if(targetIndexEntry + 1 === s){
                    result = (result[0] + result[1]) / 2;
                    break;
                }
            }
        }
        s ++;
    }
    return result;
};
function isOdd(num){
    return num % 2 === 0 ? false : true;
}

[11341684]

//利用二分法，舍弃最小的一部分和舍弃最大的一部分，递归调用，完成输出。
// 时间复杂度 O(log2(m+n))
// js中Math.log默认是以自然数e为底数，并不是以2为底数，可能会造成误导
const num1=[1,2,5,8,9,10,11];
const num2=[3,4,9,12,19,30,31];
function findMedian(num1,num2) {

    let center1Index = ~~(num1.length/2);
    let center2Index = ~~(num2.length/2);
    let center1=num1[center1Index];
    let center2=num2[center2Index];
    center1 = num1.length%2?center1:center1/2+(center1Index>0?num1[center1Index-1]:0)/2;
    center2 = num2.length%2?center2:center2/2+(center2Index>0?num2[center2Index-1]:0)/2;
    if(center1===center2){
        return center1
    }


    if(num1.length===0){
        return center2
    }
    if(num2.length===0){
        return center1
    }
    if(num1.length===1&&num2.length===1){
        return (center1+center2)/2
    }else if(num1.length===1){
        if(center1<num2[center2Index]){
            num2.splice(center2Index-(center1>num2[center2Index-1]?2:1),0,center1)
        }else {
            num2.splice(center2Index+(center1>num2[center2Index+1]?1:0),0,center1)
        }
        return findMedian([],num2);
    }else if(num2.length===1){
        if(center2<num1[center1Index]){
            num1.splice(center1Index-(center2>num1[center1Index-1]?2:1),0,center2)
        }else {
            num1.splice(center1Index+(center2>num1[center1Index+1]?1:0),0,center2)
        }
        return findMedian(num1,[]);
    }
    let rightIsMax = center2>center1;
    let spliceNumber=Math.min(center1Index,center2Index,rightIsMax?-center2Index+num2.length-1:center2Index,rightIsMax?center1Index:-center1Index+num1.length-1)||1;

    if(rightIsMax){
        num2=num2.slice(0,-spliceNumber);
        num1=num1.slice(spliceNumber);
    }else {
        num1=num1.slice(0,-spliceNumber);
        num2=num2.slice(spliceNumber);
    }
    return findMedian(num1,num2);
}
findMedian(num1,num2);