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

Question

示例 1：

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

中位数是 2.0

示例 2：

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

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

Answer 1

  let list1 = [1, 3, 5]
  let list2 = [2]

  let allLeng = list2.length + list1.length
  // 循环最大次数
  let maxCount = (allLeng / 2) | 0

  let count = 0
  let prev = null
  let current = null
  let result = null
  
  while (count <= maxCount) {
    count++
    prev = current
    if (list1.length === 0) {
      current = list2.shift()
    } else if (list2.length === 0) {
      current = list1.shift()
    } else if (list1[0] < list2[0]) {
      current = list1.shift()
    } else {
      current = list2.shift()
    }
  }

  if (allLeng % 2 === 0) { // 偶数个
    result = (prev + current) / 2
  } else { // 奇数个
    result = current
  }

  console.log(result)

Answer 2

function findMedianSortedArrays(nums1, nums2) {
  let [{ length: m }, { length: n }] = [nums1, nums2];
  if (m > n) {
    [m, n] = [n, m];
    [nums1, nums2] = [nums2, nums1];
  }
  let [imin, imax] = [0, m];
  const halfLen = (m + n + 1) / 2;
  while (imin <= imax) {
    let i = ~~((imin + imax) / 2);
    let j = ~~(halfLen - i);
    if (i < imax && nums2[j - 1] > nums1[i]) {
      imin = i + 1;
    } else if (i > imin && nums1[i - 1] > nums2[j]) {
      imax = i - 1;
    } else {
      let maxLeft;
      if (!i) {
        maxLeft = nums2[j - 1];
      } else if (!j) {
        maxLeft = nums1[i - 1];
      } else {
        maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
      }
      if ((m + n) % 2) {
        return maxLeft;
      }
      let minRight;
      if (i === m) {
        minRight = nums2[j];
      } else if (j === n) {
        minRight = nums1[i];
      } else {
        minRight = Math.min(nums2[j], nums1[i]);
      }
      return (maxLeft + minRight) / 2;
    }
  }
}

Answer 3

// 一个O(n) 的解法，在排序的基础上做二路归并。
var num1 = [1, 2, 5, 7, 10];
var num2 = [3, 4, 5, 6, 8, 9];
console.log(findMedian(num1, num2));
function findMedian(arr1, arr2) {
	var arr = [];
	if (arr1[0] >= arr2[arr2.length - 1]) {
		arr = [...arr2, ...arr1];
	} else if (arr1[arr1.length - 1] <= arr2[0]) {
		arr = [...arr1, ...arr2];
	} else {
		var arr_i = 0;
		var arr1_i = 0;
		for (var arr2_i = 0; arr2_i < arr2.length; arr2_i ++) {
			if (arr1[arr1_i] < arr2[arr2_i]) {
				arr[arr_i] = arr1[arr1_i];
				arr_i ++;
				arr1_i ++;
				arr2_i --;
			} else {
				arr[arr_i] = arr2[arr2_i];
				arr_i ++;
			}
		}
		if (arr2_i == arr2.length) {
			for (var i = arr1_i; i < arr1.length; i ++) {
				arr[arr_i] = arr1[i];
				arr_i ++;
			}
		} else {
			for (var i = arr2_i; i < arr2.length; i ++) {
				arr[arr_i] = arr2[i];
				arr_i ++;
			}
		}
	}
	if (arr.length % 2 == 0) {
		return (arr[Math.floor((arr.length - 1) / 2)] + arr[Math.floor(arr.length / 2)]) / 2;
	} else {
		return arr[Math.floor(arr.length / 2)];
	}
}

Answer 4

代码不复杂，就是原本想能一行写完写成了这样，有点难读

const findMedianSortedArrays = (nums1, nums2) => {
  let len = nums1.length + nums2.length
  if (len <= 2) return ((nums1.length === 0 ? 0 : nums1.reduce((x, val) => x + val)) + (nums2.length === 0 ? 0 : nums2.reduce((x, val) => x + val))) / len;
  ((nums1.lenght !== 0 && (nums2.length ===0 || (nums1[nums1.length - 1] > nums2[nums2.length - 1]))) ?nums1 : nums2).pop();
  (nums1.length !== 0 && (nums2.length === 0 || (nums1[0] < nums2[0])) ? nums1 : nums2).shift()
  return findMedianSortedArrays(nums1, nums2)
}

• 执行用时 :132 ms, 在所有 JavaScript 提交中击败了75.54%的用户
• 内存消耗 :39.4 MB, 在所有 JavaScript 提交中击败了93.75%的用户

或者不用递归

const findMedianSortedArrays = (nums1, nums2) => {
  while (nums1.length + nums2.length > 2) {
    ((nums1.lenght !== 0 && (nums2.length === 0 || (nums1[nums1.length - 1] > nums2[nums2.length - 1]))) ? nums1 : nums2).pop();
    (nums1.length !== 0 && (nums2.length === 0 || (nums1[0] < nums2[0])) ? nums1 : nums2).shift()
  }
  return ((nums1.length === 0 ? 0 : nums1.reduce((x, val) => x + val)) + (nums2.length === 0 ? 0 : nums2.reduce((x, val) => x + val))) / (nums1.length + nums2.length);
}

• 执行用时 :136 ms, 在所有 JavaScript 提交中击败了67.91%的用户
• 内存消耗 :39.3 MB, 在所有 JavaScript 提交中击败了93.75%的用户

Answer 5

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/

Answer 6

/**
 * 因为已经是有序数组，所以不需要递归调用来排序，只需要借鉴归并排序中两个有序数组合并的算法就可以
 * @param {*} nums1 
 * @param {*} nums2 
 */
function findMidValue(nums1, nums2) {

    let nums = [];

    //合并两个有序数组
    while (nums1.length && nums2.length) {
        if (nums1[0] < nums2[0]) {
            nums.push(nums1.shift())
        } else {
            nums.push(nums2.shift());
        }
    }

    if (nums1.length) {
        nums.push(...nums1);
    }

    if (nums2.length) {
        nums.push(...nums2);
    }

    let len = nums.length;
    let midValue = 0;

    console.log('nums:', nums);

    if (len % 2 === 0) {
        midValue = (nums[len / 2] + nums[len / 2 - 1]) / 2;
    } else {
        midValue = nums[Math.floor(len / 2)];
    }


    return midValue;
}

var nums1 = [1, 2]
var nums2 = [3, 4, 6, 8]

console.log(findMidValue(nums1, nums2));

Answer 7

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let index = 0;
    let len = nums1.length + nums2.length;
    let val0;
    let val1;
    let i = 0;
    let j = 0;
    let mid = ~~((len + 2) / 2);

    while(index < mid){
        val0 = val1;
        if(i >= nums1.length){
            val1 = nums2[j];
            j ++;
        }else if(j >= nums2.length){
            val1 = nums1[i];
            i ++;
        }else if(nums1[i] >= nums2[j]){
            val1 = nums2[j];
            j ++;
        }else{
            val1 = nums1[i];
            i ++;
        }
        index ++;
    }
    return len % 2 === 1 ? val1 : (val1 + val0)/2
};

120 ms

Answer 8

/**
 * @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

请教一下，这个的复杂度不是O(log(m+n))吧，应该是O(m+n)

Answer 9

var findMedianSortedArrays = function(nums1, nums2) {
    //先归并 归并结束求中位数
    var arr = [];
    while(nums1.length|| nums2.length){
        if(nums1.length==0&&nums2.length){
            arr = [...arr,...nums2];
            break;
        }
        if(nums2.length==0&&nums1.length){
            arr = [...arr,...nums1];
            break;
        }
        if(nums1[0]<=nums2[0]){
            arr.push(nums1.shift());
        }else{
            arr.push(nums2.shift());
        }
       
    }
    var half = Math.ceil(arr.length/2);
    if(arr.length%2==0){
        return (arr[half] + arr[half-1])/2;
    }else{
        return arr[half-1];
    }   
};

Answer 10

/**
 * 使用归并思想,时间复杂度O(log(m+n))
 * @param {*} arr1 
 * @param {*} arr2 
 */
const getMidPointNumber = (arr1, arr2) => {
    let arr = []
    let len = arr1.length + arr2.length
    let index = 0
    let mid = Math.floor(len / 2)
    while (arr1.length > 0 || arr2.length > 0) {
        if (index > mid) {
            if (len % 2 !== 0) {
                return arr[index - 1]
            } else {
                return (arr[index - 2] + arr[index - 1]) / 2
            }
        }
        if (arr1.length > 0 && arr2.length > 0) {
            arr.push(arr1[0] > arr2[0] ? arr2.shift() : arr1.shift())
        } else if (arr1.length > 0) {
            arr.push(arr1.shift())
        } else {
            arr.push(arr2.shift())
        }
        index++
    }
    if (arr.length === 1) return arr[0]
    return (arr[0] + arr[1]) / 2
}

Answer 11

var findMedianSortedArrays = function (nums1, nums2) {
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }

  var len1 = nums1.length;
  var len2 = nums2.length;

  var low = 0;
  var high = len1;

  while (low <= high) {
    var p1 = Math.floor((low + high) / 2);
    var p2 = Math.ceil((len1 + len2) / 2) - p1;

    var maxLeft1 = p1 === 0 ? -Infinity : nums1[p1 - 1];
    var minRight1 = p1 === len1 ? Infinity : nums1[p1];
    var maxLeft2 = p2 === 0 ? -Infinity : nums2[p2 - 1];
    var minRight2 = p2 === len2 ? Infinity : nums2[p2];

    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      if ((len1 + len2) % 2 === 0) {
        return (
          (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2
        );
      } else {
        return Math.max(maxLeft1, maxLeft2);
      }
    } else if (maxLeft1 > minRight2) {
      high -= 1;
    } else {
      low += 1;
    }
  }
};

https://www.youtube.com/watch?v=LPFhl65R7ww
推荐这个视频，图文并茂，生动形象，容易理解，时间复杂度O(log min(m, n))

Answer 12

function findMiddle(arr1, arr2) {
    let arr = [...arr1, ...arr2].sort((a,b)=> return a-b)
    let num = arr.length%2
    return num === 1 ? arr[Math.floor(len/2)] : (arr[arr.length/2]-1 + arr[arr.length/2])/2
}
arr = [1,2,3,4,5,6,7,8]
findMiddle(arr)

Answer 13

大顶堆+小顶堆

const defaultCmp = (x, y) => x > y; // 默认是大顶堆

const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);

class Heap {
  /**
   * 默认是大顶堆
   * @param {Function} cmp
   */
  constructor(cmp = defaultCmp) {
    this.container = [];
    this.cmp = cmp;
  }

  insert(data) {
    const { container, cmp } = this;

    container.push(data);
    let index = container.length - 1;
    while (index) {
      let parent = Math.floor((index - 1) / 2);
      if (!cmp(container[index], container[parent])) {
        return;
      }
      swap(container, index, parent);
      index = parent;
    }
  }

  extract() {
    const { container, cmp } = this;
    if (!container.length) {
      return null;
    }

    swap(container, 0, container.length - 1);
    const res = container.pop();
    const length = container.length;
    let index = 0,
      exchange = index * 2 + 1;

    while (exchange < length) {
      // 以大顶堆的情况来说：如果有右节点，并且右节点的值大于左节点的值
      let right = index * 2 + 2;
      if (right < length && cmp(container[right], container[exchange])) {
        exchange = right;
      }
      if (!cmp(container[exchange], container[index])) {
        break;
      }
      swap(container, exchange, index);
      index = exchange;
      exchange = index * 2 + 1;
    }

    return res;
  }

  top() {
    if (this.container.length) return this.container[0];
    return null;
  }
}
var MedianFinder = function () {
  this.maxHeap = new Heap();
  this.minHeap = new Heap((x, y) => x < y);
};

MedianFinder.prototype.addNum = function (num) {
  this.maxHeap.insert(num);
  this.minHeap.insert(this.maxHeap.top());
  this.maxHeap.extract();

  if (this.maxHeap.container.length < this.minHeap.container.length) {
    this.maxHeap.insert(this.minHeap.top());
    this.minHeap.extract();
  }
};

MedianFinder.prototype.findMedian = function () {
  return this.maxHeap.container.length > this.minHeap.container.length
    ? this.maxHeap.top()
    : (this.maxHeap.top() + this.minHeap.top()) / 2;
};

// 使用
let finder = new MedianFinder()
let nums1 = [1, 2]
let nums2 = [3, 4]
for(let i of nums1){
    finder.addNum(i)
}
for(let i of nums2){
    finder.addNum(i)
}
console.log(finder.findMedian())

Answer 14

加了注释，好理解一点，时间复杂度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)
  }
}

太秀了，留下了没有技术的泪水，给我抄我都抄不会

Answer 15

示例 1：

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

中位数是 2.0

示例 2：

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

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

function medianNum(arr1, arr2) {
let arr = [...arr1, ...arr2].sort((a,b) => a-b)
let len = arr.length
let index = parseInt(len/2)
let num = null
if (len%2 == 0) {
num = (arr[index] + arr[index - 1])/2
} else {
num = arr[index]
}console.log(num)
}

Answer 16

var findMedianSortedArrays = function(nums1, nums2) {
    var length1 = nums1.length;
    var length2 = nums2.length;
    var nums3 = [];
    var j = 0, k = 0;

    while (j + k < (length1 + length2) / 2 + 1) {
        if (nums1[j] === undefined) {
            nums3.push(nums2[k++]);
        } else if (nums2[k] === undefined) {
            nums3.push(nums1[j++]);
        } else if (nums1[j] < nums2[k]) {
            nums3.push(nums1[j++]);
        } else {
            nums3.push(nums2[k++]);
        }
    }
    var length3 = nums3.length;
    if ((length1 + length2) % 2) {
        return nums3[length3 - 2];
    } else {
        return (nums3[length3 - 2] + nums3[length3 - 1]) / 2;
    }
};

Answer 17

function getMedian(m, n) {
	let tempArr = [];
	while (m.length && n.length) {	//合并两数组
		if (m[0] < n[0]) {
			tempArr.push(m.shift())
		} else {
			tempArr.push(n.shift())
		}
	}
	tempArr = tempArr.concat(m, n); //连接未处理的数据，获得数组合并后的所有值
	let res;
	let middle = (tempArr.length - 1) / 2;	//中间索引位置，这里分两种情况，如果数组长度为偶数则为中间两数均值，如为奇数则为当前索引的数组元素
	res = tempArr.length % 2 === 0 ? (tempArr[Math.floor(middle)] + tempArr[Math.ceil(middle)]) / 2 : tempArr[
		middle];
	return res;
}
console.log(getMedian([1,3,9], [3,3,5]));

Answer 18

// 求有序数组中位数
function fm(){
  // let a1 = [1,2,3,4,5,6,7,8]
  // let a2 = [9,10,11,12,13,14,15,16,17]
  let a1 = [2,3,4,5,6,7]
  let a2 = [1]
  let k = Math.ceil((a1.length+a2.length)/2) // 9
  let isOdd = (a1.length + a2.length)%2 === 1
  // 求第k小的数 
  function fun(arr1,arr2,z){
    if(z === 1){
      if(isOdd){
        if(!arr1.length){
          return arr2[z-1]
        }
        if(!arr2.length){
          return arr1[z-1]
        } 
        return arr1[z-1] > arr2[z-1] ? arr2[z-1] : arr1[z-1]
      }else{
        if(!arr1.length){
          return (arr2[z-1] + arr2[z]) / 2
        }
        if(!arr2.length){
          return (arr1[z-1] + arr1[z]) / 2
        }
        let _arr = arr1.slice(0,2).concat(arr2.slice(0,2)).sort((a,b)=>{
          return a - b
        })
        return (_arr[0] + _arr[1]) / 2
      }
    }
    
    let idx = Math.floor(z/2)
    if(arr1.length !== 0){
      idx = arr1[idx-1] === undefined ? arr1.length : idx
    }
    if(arr2.length!==0 ){
      idx = arr2[idx-1] === undefined ? arr2.length : idx
    }
    if(arr2.length===0 || arr1[idx-1] <= arr2[idx-1]){
      arr1 = arr1.slice(idx)
    }else{
      arr2 = arr2.slice(idx)
    }
    z -= idx
    return fun(arr1,arr2,z)
  }
  let res = fun(a1,a2,k)
  return res
}

Answer 19

试了一下OK的

var findMedianSortedArrays = function (nums1, nums2) {
    let i = 0, j = 0
    const len = nums1.length + nums2.length
    let res = []
    let result = 0
    while (i < nums1.length || j < nums2.length) {
        if (nums1[i] && nums2[j]) {
            if (nums1[i] < nums2[j]) {
                res.push(nums1[i])
                i++
            } else if (nums1[i] >= nums2[j]) {
                res.push(nums2[j])
                j++
            }
        }
        if (nums1[i] && !nums2[j]) {
            res.push(nums1[i])
            i++
        }
        if (!nums1[i] && nums2[j]) {
            res.push(nums2[j])
            j++
        }
        // 单独判断为0的情况
        if (nums1[i] == 0) {
            res.push(nums1[i])
            i++
        }
        if (nums2[j] == 0) {
            res.push(nums2[j])
            j++
        }
    }
    if (len % 2 == 1) {
        result = res[Math.floor(len / 2)]
    } else {
        result = (res[len / 2 - 1] + res[len / 2]) / 2
    }
    return result
};

Answer 20

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

Answer 21

/**
 * @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;
}

Answer 22

//利用二分法，舍弃最小的一部分和舍弃最大的一部分，递归调用，完成输出。
// 时间复杂度 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);

Answer 23

力扣上一道题，不会做
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu-b/

Answer 24

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

二分法就是

Answer 25

var findMedianSortedArrays = function(nums1, nums2) {
    return find2Middle(nums1, nums2)
}

var findMiddle = (arr) => {
  let L = arr.length
  if (L < 3) return sum(arr)/L
  newArr = arr.slice(1, -1)
  return findMiddle(newArr)
}

var sum = (arr) => arr.reduce((a, c) => a + c, 0)

var find2Middle = (M, N) => {
  let LengthM = M.length, LengthN = N.length
  if (LengthM === 0) return findMiddle(N)
  if (LengthN === 0) return findMiddle(M)
  if (LengthM + LengthN === 2) return (M[0]+N[0])/2

  let newM = M, newN = N;
  let ML = M[0], MH = M[LengthM - 1];
  let NL = N[0], NH = N[LengthN - 1];

  if (ML <= NL) newM = M.slice(1);
  if (ML > NL) newN = N.slice(1);

  if (MH <= NH) newN = newN.slice(0, -1);
  if (MH > NH) newM = newM.slice(0, -1);

  return find2Middle(newM, newN);
}

随便写的, 求大神指点

2084 / 2084 test cases passed.	Status: Accepted
Runtime: 120 msMemory Usage: 69.6 MB

Answer 26

sort

sort 底层实现是什么啊

Answer 27

这是一个leetcode原题， 题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays .

官方中文版链接： https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

以下我的答案：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
function findKth(nums1, nums2, k) {
  if (nums1.length === 0) return nums2[k - 1];
  if (nums2.length === 0) return nums1[k - 1];
  if (k == 1) return Math.min(nums1[0], nums2[0]);
  let i = Math.min(k >> 1, nums1.length);
  let j = Math.min(k >> 1, nums2.length);
  if (nums1[i - 1] > nums2[j - 1]) {
    return findKth(nums1, nums2.slice(j), k - j);
  }

  return findKth(nums1.slice(i), nums2, k - i);
}
var findMedianSortedArrays = function(nums1, nums2) {
  // 1 
  // 2 3 4 5
  const m = nums1.length,
    n = nums2.length;
  return (
    (findKth(nums1, nums2, (m + n + 1) >> 1) +
      findKth(nums1, nums2, (m + n + 2) >> 1)) /
    2.0
  );
};

如果大家对算法有兴趣，可以关注下我的仓库《leetcode题解》

Answer 28

推荐：https://mp.weixin.qq.com/s/OE4lHO8-jOIxIfWO_1oNpQ

Answer 29

两个指针扫，排序，排到中位数 ，返回结果

Answer 30

// 时间复杂度为O(M+N)的依次比较排序
function sortMN(arr1,arr2) {
	let i=j=0;
	const arr1length = arr1.length;
	const arr2length = arr2.length;
	let arr = [];
	while(i< arr1length && j< arr2length) {
		if (arr1[i] < arr2[j]){
			arr.push(arr1[i])
			i++
		} else {
			arr.push(arr2[j])
			j++
		}
	}
	if(i === arr1length){
		arr.concat(arr2.slice(j));
	} else {
		arr.concat(arr1.slice(i))
	}
	return arr
}
function middleNumber(arr1,arr2) {
	let arr = sortMN(arr1,arr2);
	let arrLength = arr.length;
    if (arrLength % 2 === 0) {
    	return (arr[arrLength/2] + arr[arrLength/2-1]) / 2.00
    } else {
    	eturn arr[arrLength/2]
    }
}

Answer 31

题目已经说明了是两个有序数组，那可以按照归并排序的方法进行数组合并

function findMiddle(arr1,arr2){
    var result = [];
    while(arr1.length && arr2.length){
        if(arr1[0]<arr2[0]){
            result.push(arr1[0]);
            arr1.shift();
        }else{
            result.push(arr2[0]);
            arr2.shift();
        }
    }
    if(arr1.length){
        result = result.concat(arr1);
    }
    if(arr2.length){
        result = result.concat(arr2);
    }
    return result.length%2===0 
        ? (result[Math.floor(result.length/2)-1] + result[Math.floor(result.length/2)])/2
        : result[Math.floor(result.length/2)];

}

Answer 32

我连中位数是啥都不知道 留下了没有技术的眼泪

Answer 33

对于一个有序数组来说，

如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；
如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数
所以我们首先要将两个有序数组进行合并，再进行中位数计算

function sort(arr1, arr2) {
	let index1 = 0 // 数组1下标
	let index2 = 0 // 数组2下标
	let arr = []  // 合并后的数组
        // 只要有一个有序数组的下标和该数组长度相等，就停止循环♻️
	while(index1 < arr1.length && index2 < arr2.length) {
		if(arr1[index1] < arr2[index2]) {
			arr.push(arr1[index1])
			index1++
		} else {
			arr.push(arr2[index2])
			index2++
		}
	}
        // 判断是哪个数组的下标和长度相等，再将另一个数组进行合并
	if(index1 === arr1.length) {
                // concat不会改变现有的数组，而仅仅会返回被连接数组的一个副本，所以需要重新赋值给arr
		arr = arr.concat(arr2.slice(index2, arr2.length)) 
	}
	if(index2 === arr2.length) {
		arr = arr.concat(arr1.slice(index1, arr1.length))
	}
	if(arr.length % 2 === 0) {
		return (arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2
	}else {
		return arr[Math.floor(arr.length / 2)]
	}
}

Answer 34

function mid (arr1, arr2) {
const len1 = arr1.length;
const len2 = arr2.length;

const len = len1 + len2;

let arr = [];

let i = 0, j = 0, k = 0;

while(i < len1 && j < len2 && k < len) {
	if (arr1[i] < arr2[j]) {
		arr[k++] = arr1[i++];
	} else {
		arr[k++] = arr2[j++];
	}
}

if (i < len1) {
	arr = [...arr, ...arr1.slice(i)];
}

if (j < len2) {
	arr = [...arr, ...arr2.slice(j)];
}

if (len % 2 == 0) {
	return (arr[Number.parseInt(len / 2) - 1] + arr[Number.parseInt(len / 2) + 1]) / 2;
} else {
	return arr[Number.parseInt(len / 2)];
}

}

Answer 35

大佬们 我这个能否达标？

leetcode上 144ms-208ms 之间 符合O(log(m+n))这个复杂度吗？
我的思路：
两个数组依次比较同时用n1、n2记住位置
当比较次数达到两个数组总长度一半时返回结果

var findMedianSortedArrays = function (nums1, nums2) {
    let sum = nums1.length + nums2.length,
     count = 0,
     n1 = 0,
     n2 = 0,
     half = Math.floor(sum / 2 + 1),
     res = [];
     while (count < half) {
         if (nums1[n1] <= nums2[n2] || nums2[n2] === undefined) {
             res.push(nums1[n1])
             n1++;
         } else {
             res.push(nums2[n2])
             n2++;
         }
         count++;
     }
     if (sum % 2 == 0) {
         return (res[res.length - 1] + res[res.length - 2]) / 2;
     } else {
         return res[res.length - 1];
    }
};

Answer 36

function midNum(nums1, nums2){
    let nums = [...nums1, ...nums2];
    nums.sort((a, b) => a-b)
    let length = nums.length;
    if(length % 2 == 1){
        return nums[(length-1)/2]
    }
    return (nums[length/2]+nums[length/2-1])/2;
}

Answer 37

function middle(arr1, arr2) {
	let o = arr1.concat(arr2).sort(function (a,b) {
		return a - b
	});
	let middleNum;
	if (o.length % 2 === 0) { // 偶数
		middleNum = (o[o.length / 2] + o[o.length / 2 - 1]) / 2
	} else { // 奇数
		middleNum = o[parseInt(o.length / 2)]
	}
	console.log(`中位数为 ${middleNum}`);
}

Answer 38

先合并两个有序数组

  var mergetTwoArrays = (nums1, nums2) =>{
       var i = 0
       var m = 0, lenM = nums1.length
       var n = 0, lenN = nums2.length
       var arr = []
       while(m < lenM && n < lenN) {
         if (nums1[m] <= nums2[n]) {
          arr[i++] = nums1[m++]
         } else {
          arr[i++] = nums2[n++]
         }
       }
      while(n < lenN) {
        arr[i++] = nums2[n++]
      }
      while(m < lenM) {
        arr[i++] = nums1[m++]
      }
      return arr
  }

然后求中位数，但是时间复杂度为O(m + n)

Answer 39

类似归并排序最后一大步的思路，不排序直接找中位数
逐步去除最大最小数，逼近中位数

const quickMid = (nums1, nums2) => {
 
  let n = Math.ceil((nums2.length + nums1.length) / 2)

  let i1Start = i2Start = 0
  let i1End = nums1.length -1, i2End = nums2.length - 1

  let newNum

  for (let i = 0; i < n - 1; i++) { // n-1 最后一组不比较
    let min1 = nums1[i1Start]
    let min2 = nums2[i2Start]

    min1 === undefined || min1 > min2 ? i2Start++ : i1Start++

    let max1 = nums1[i1End]
    let max2 = nums2[i2End]

    max1 === undefined || max2 > max1 ? i2End-- : i1End--

    // 一组先结束取另一组剩余值
    if (i1Start > i1End) {
      newNum = nums2.slice(i2Start, i2End + 1)
      break
    } else if (i2Start > i2End) {
      newNum = nums1.slice(i1Start, i1End + 1)
      break
    }
  }

  if (newNum) {
    let l = newNum.length
    let mid = Math.ceil(l / 2)
    if (l % 2 === 0) {
      return (newNum[mid] + newNum[mid - 1]) / 2
    } else {
      return newNum[mid - 1]
    }
  } else {
    num1 = i1Start === i1End ? nums1[i1End] : nums1[i1Start + 1]
    num2 = i2Start === i2End ? nums2[i2End] : nums2[i2Start + 1]
    return (num1 + num2) / 2
  }
}

Answer 40

思路：只要找到这两个有序数组的中位数，那么我们可以首先算出两个数组的长度和，然后推算出中位数所在的索引，如果长度为奇数，那么就是n/2,如果是偶数，那么是n/2 和n/2-1，我们对两个数组进行排序时（因为已经是有序数组，所以可以采用类似归并的算法，整合两个数组，循环结束条件即为数组长度=中位数的索引+1），然后最后得到中位数， 这样可以吗？
const nums1 = [1, 5, 5.5, 7, 8, 9]
const nums2 = [2, 3, 5, 6, 8.5, 10]

const len = Math.round((nums1.length + nums2.length) / 2)
const res = []
let i = 0, j = 0
while (res.length <= len + 1) {
// 合并两个有序数组
if (nums1[i] < nums2[j]) {
res.push(nums1[i])
i++
} else {
res.push(nums2[j])
j++
}
}
console.log(res)
if ((nums1.length + nums2.length) % 2) { //奇数位
console.log(res[len - 1])
} else { //偶数位
console.log((res[len] + res[len - 1]) / 2)
}

Answer 41

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

Answer 42

/**
 * @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

Answer 43

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

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

Answer 44

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]
  }

提交结果	执行用时
通过

Answer 45

@Molunerfinn 老哥，厉害了！

Answer 46

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

Answer 47

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

Answer 48

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

Answer 49

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]
    }
};

Answer 50

加了注释，好理解一点，时间复杂度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)
  }
}

Answer 51

想到一个 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];
    }
  };