4. [✔][H]寻找两个正序数组的中位数

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 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

提示：

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

---

题解：

这个难点在于循环条件的指定 i <= Math.floor(len / 2)，以及判断条件该选用nums1的值还是nums2的值if (l1 < m && (nums1[l1] < nums2[l2] || l2 >= n)) {

/*
 * @lc app=leetcode.cn id=4 lang=typescript
 *
 * [4] 寻找两个正序数组的中位数
 */

// @lc code=start
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    let m = nums1.length;
    let n = nums2.length;

    let len = m + n;
    let preValue = -1;
    let curValue = -1;
    let l1 = 0;
    let l2 = 0;

    for (let i = 0; i <= Math.floor(len / 2); i++) {
        preValue = curValue;
        // 为什么加l2 >= n？因为此时l2已经超出了n，nums2[l2] = undefined，如果不再上面添加这个条件
        // l2会还往后+1，如果添加了，相当于结束为止在l1上
        if (l1 < m && (nums1[l1] < nums2[l2] || l2 >= n)) {
            curValue = nums1[l1];
            l1++;
        } else {
            curValue = nums2[l2];
            l2++;
        }
    }

    return len % 2 === 0 ? (preValue + curValue) / 2 : curValue;

};
// @lc code=end