寻找两个正序数组的中位数

[sisterAn]

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10⁶ <= nums1[i], nums2[i] <= 10⁶

**进阶：**你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

leetcode

[xiaoerwen]

const findMedianSortedArrays = (nums1, nums2) => {
    if (!nums1.length && !nums2.length) {
        return null;
    }

    // 如果数组1为空
    if (!nums1.length) {
        // 若此时数组2仅一个值，那么该值为中位数
        if (nums2.length === 1) {
            return nums2[0];
        }

        /** 
         * 否则比较数组2，取中位数
         * 比较单个数组采用二分法
         */
        let half = Math.floor(nums2.length / 2);
        return findMedianSortedArrays(nums2.slice(0, half), nums2.slice(half));
    }

    // 如果数组2为空，同理
    if (!nums2.length) {
        if (nums1.length === 1) {
            return nums1[0];
        }

        let half = Math.floor(nums1.length / 2);
        return findMedianSortedArrays(nums1.slice(0, half), nums1.slice(half));
    }

    // 如果两个数组都只剩1个数，取两者中间值
    if (nums1.length === 1 && nums2.length === 1) {
        return nums1[0] === nums2[0] ? nums1[0] : (nums1[0] + nums2[0]) / 2;
    }

    // 比较两个数组的最小值，丢弃最小值
    nums1[0] < nums2[0] ? nums1.shift() : nums2.shift();

    /**
     * 这里注意边界值，丢弃最小值后有的数组可能为空
     */
    if (!nums1.length) {
        // 强制丢掉最大值
        nums2.pop();
        return findMedianSortedArrays(nums1, nums2);
    }
    if (!nums2.length) {
        nums1.pop();
        return findMedianSortedArrays(nums1, nums2);
    }

    // 比较两个数组的最大值，丢弃最大值
    nums1[nums1.length - 1] > nums2[nums2.length - 1] ? nums1.pop() : nums2.pop();
    // 重复该操作
    return findMedianSortedArrays(nums1, nums2);
};

思路：比较两个有序数组的最小值与最大值，剔除最大最小值后重新比较
重复此操作，直到剩余1个数，那么该数为中位数
如果剩余2个数，那么中位数为两者和除2
单数组采用二分法

注意：边界值比较多

该题耗时：20ms（击败了99%），内存消耗：41.9M（击败了94%）

[Upting]

来个简单点的：

const arr1 = [1, 2, 10];
const arr2 = [2, 5, 7, 8];

function findMiddleNumber(arr1, arr2) {
        // 容错处理
        if (!arr1.length && !arr2.length) return null;
	// 合并并排序
	const total = [...arr1, ...arr2].sort((a, b) => a - b);
	// 中位数索引
	let midIndex = (total.length - 1) / 2;

	// 两位
	if (String(midIndex).includes(".")) {
		const left = parseInt(midIndex);
		const right = parseInt(midIndex) + 1;
		const midNumber = (total[left] + total[right]) / 2;
		return midNumber.toFixed(5);
	} else {
		// 一位
		return total[midIndex].toFixed(5);
	}
}

console.log(findMiddleNumber(arr1, arr2));