这是我参与更文挑战的第 18 天，活动详情查看更文挑战

这个系列没啥花头，就是纯 leetcode 题目拆解分析，不求用骚气的一行或者小众取巧解法，而是用清晰的代码和足够简单的思路帮你理清题意。让你在面试中再也不怕算法笔试。

126. 寻找两个正序数组的中位数 (median-of-two-sorted-arrays)

题目

这里不贴题了，leetcode打开就行，题目大意：

给定两个大小分别为 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 = [], nums2 = [1]
输出：1.00000
复制代码

基本思路

我们先了解下定义：

中位数（又称中值，英语：Median），统计学中的专业名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为数量相等的上下两部分。对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，则中位数不唯一，通常取最中间的两个数值的平均数作为中位数。

性质

一个数集中最多有一半的数值小于中位数，也最多有一半的数值大于中位数。
如果大于和小于中位数的数值个数均少于一半，那么数集中必有若干值等同于中位数。

思路：

合并成大数组

就是两个合并成大的升序数组，需要新开空间。
得到大数组后判断奇偶，分别取中间位置的数或平均值返回即可。

写法实现

var findMedianSortedArrays = function(nums1, nums2) {
    // 合并函数
    const merge = (arr1, arr2) => {
        let merged = [...arr1, ...arr2]
        return merged.sort((a, b) => a - b)
    }
    // 直接把两个数组合并位一个大的升序数组，然后获得中位数
    let mergedArr = merge(nums1, nums2);
    let len = mergedArr.length
    if (len % 2 !== 0) {
        // 如果是奇数，取中间位置即可
        return mergedArr[(len - 1) / 2]
    } else {
        // 如果是偶数，中间两个取平均
        return (mergedArr[len / 2 - 1] + mergedArr[len / 2]) / 2
    }
};  

let nums1 = [1,2], nums2 = [3,4]
console.log(findMedianSortedArrays(nums1, nums2))
复制代码

127. 除自身以外数组的乘积 (product-of-array-except-self)

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在O(n) 时间复杂度内完成此题。

进阶：
你可以在常数空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

示例 1：

输入: [1,2,3,4]
输出: [24,12,8,6]
复制代码

基本思路

注意限制不能使用除法。

不含该数其他位置的乘积，我们可以先分解为该数的左边乘积 * 右边乘积，然后

我们以 nums = [1, 2, 3, 4] 为例：

从左遍历 nums ，每个元素的左边积存到 res

    nums = [1, 2, 3, 4]
// 1 没有左边, 初始值设置 1，1乘任何数都没关系
// 2 的左边就是 1 * 1
// 3 的左边是 1 * 1 * 2
就是 [1, 1*1, 1*1*2, 1*1*2*3] 得到 [1, 1, 2, 6]
[1 1 2 6] 可看做原数组每个位置 左边数的乘积
复制代码

再从右遍历 nums，用一个变量保存当前元素的右边积，让它和当前 res[i] 相乘（即当前的左边积），存结果 res[i]
然后更新右边积

写法实现

var productExceptSelf = (nums) => {
    // 数组第一项没有左边数，初始化 * 1
    let [res, len] = [[1], nums.length]

    // 遍历nums先把左边所有元素乘积算出
    for (let i = 1; i < len; i++) {
        // res[i] 现在是 nums[i] 的左边乘积
        res[i] = res[i - 1] * nums[i - 1]
    }
    // r_acc 保存当前迭代右边所有乘积，同样最右边初始化 1
    let r_acc = 1
    // 从右向左遍历
    for (let i = len - 1; i >= 0; i--) {
        // 此时 res[i] 中是左边积再乘上右边积，就是最后的结果输出
        res[i] = res[i] * r_acc
        // 更新当前位置右边积，给下一轮来乘
        r_acc = nums[i] * r_acc 
    }
    return res
}

let nums = [1,2,3,4]
console.log(productExceptSelf(nums))
复制代码

另外向大家着重推荐下这个系列的文章，非常深入浅出，对前端进阶的同学非常有作用，墙裂推荐！！！核心概念和算法拆解系列

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦点击此处交个朋友
Or 搜索我的微信号infinity_9368，可以聊天说地
加我暗号 “天王盖地虎” 下一句的英文，验证消息请发给我
presious tower shock the rever monster，我看到就通过，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧