第 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

[sexnmaa]

试了一下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
};

[Yangfan2016]

难点在于选择好排序算法

[benzhemin]

Dived the whole numbers into 2 groups: to make sure left side is less or equal to the right side.

Fomular:

1. partitionX + partitionY = (lenX + lenY + 1)/2
2. maxLeftX <= minRightY maxLeftY <= minRightX

Time complexity: log(min(m,n))

const findMediumFromSortedArrays = (itemListA, itemListB) => {
    const lenA = itemListA.length;
    const lenB = itemListB.length;

    if (lenA > lenB) {
        return findMediumFromSortedArrays(itemListB, itemListA);
    }

    let start = 0, end = lenA;
    while (start < end) {

        const x = Math.floor((start + end) / 2);
        const y = Math.floor((lenA + lenB + 1) / 2) - x;

        // find correct x position
        if (itemListA[x-1] <= itemListB[y] && itemListB[y-1] <= itemListA[x]) {
            // should be in max left & min right
            console.log(x, y);
        } else if (itemListA[x-1] > itemListB[y]) {
            end = Math.floor((start + end) / 2);
        } else {
            start = Math.floor((start + end) / 2);
        }
    }
}

const itemListA = [1, 3, 8, 9, 15];
const itemListB = [7, 11, 18, 19, 21, 25];

findMediumFromSortedArrays(itemListA, itemListB)

The skeleton of the algorithm.

https://www.youtube.com/watch?v=LPFhl65R7ww

[qifengla]

function midOfTwoArray(arr1, arr2) {
    if (arr1.length > arr2.length) {
        [arr1, arr2] = [arr2, arr1];
    }
    let [m, n] = [arr1.length, arr2.length];

    let [mid1, left1, right1, mid2, left2, right2] = [Math.floor(m / 2), 0, m - 1, Math.floor(n / 2), 0, n - 1];
    while (left1 <= right1) {
        if (arr1[mid1] === arr2[mid2]) {
            return arr1[mid1];
        }
        else if (arr1[mid1] < arr2[mid2]) {
            left1 = mid1 + 1;
            mid1 = Math.floor((left1 + right1) / 2);
            mid2 = mid2 - (mid1 - left1);
        }
        else {
            right1 = mid1 - 1;
            mid1 = Math.floor((left1 + right1) / 2);
            mid2 = mid2 + (right1 - mid1);
        } 
    }
    return (arr1[mid1] + arr2[mid2]) / 2;
}

// 示例用法
const nums1 = [1, 3];
const nums2 = [2];
console.log(midOfTwoArray(nums1, nums2)); // 输出 2.0

[XW666]

  var findMedianSortedArrays = function (nums1, nums2) {
    let list = [...nums1, ...nums2]
    //冒泡排序
    for (let i = 0; i < list.length - 1; i++) {
      for (let j = i + 1; j < list.length; j++) {
        let tmep = list[i]
        if (list[j] < tmep) {
          list[i] = list[j]
          list[j] = tmep
        }
      }
    }
    let len = list.length
    let mid = Math.floor(list.length / 2)

    if (len % 2 === 0) {

      return (list[mid] + list[mid - 1]) / 2
    } else {
      return list[mid]
    }
  };

[zhaocchen]

思路：二分 关键：logn的时间复杂度一般使用二分

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
    const len1 = nums1.length, len2 = nums2.length;

    // 寻找两个正序数组的第k个元素
    const getKth = (k) => {
        let i = 0, j = 0;
        while (true) {
            if (i == len1) return nums2[j + k - 1];
            if (j == len2) return nums1[i + k - 1];
            if (k == 1) {
                return Math.min(nums1[i], nums2[j]);
            }

            const half = k >> 1;
            const x = Math.min(i + half, len1) - 1,
                y = Math.min(j + half, len2) - 1;
            if (nums1[x] <= nums2[y]) {
                // 移动i指针
                k -= (x - i + 1);
                i = x + 1;
            } else {
                // 移动j指针
                k -= (y - j + 1);
                j = y + 1;
            }
        }
    }

    const totalLen = len1 + len2;
    if (totalLen & 1) {
        return getKth((totalLen + 1) >> 1);
    } else {
        return (getKth((totalLen + 1) >> 1) + getKth((totalLen + 2) >> 1)) / 2;
    }
};

[961998264]

function test1(m,n) {

let mMin = Infinity,nMin = Infinity let mMax = -Infinity,nMax = -Infinity for(let i of m){ mMin = Math.min(mMin,i) mMax = Math.max(mMax,i) } for(let i of n){ nMax = Math.max(nMax,i) nMin = Math.min(nMin,i) }

return (Math.min(mMin,nMin)+ Math.max(mMax,nMax)) / 2 }