关于后端:面试题-1719-消失的两个数字-简单数学运用题

这是 LeetCode 上的 面试题 17.19. 隐没的两个数字 ，难度为艰难。

Tag :「数学」

给定一个数组，蕴含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 $O(N)$ 工夫内只用 $O(1)$ 的空间找到它们吗？

以任意程序返回这两个数字均可。

示例 1:

输出: [1]

输入: [2,3]

示例 2:

输出: [2,3]

输入: [1,4]

提醒：

$nums.length <= 30000$

依据题意，给定 nums 的长度为 $m$ 且缺失了两个数，所有的 $nums[i]$ 加上缺失数字组成间断排列长度为 $n = m + 2$。

依据等差数量求和公式可知，补齐后的排列总和为 $\frac{n \times (1 + n)}{2}$，补全后的实践总和与理论总和之间的差值 $cur = \frac{n \times (1 + n)}{2} – \sum_{i = 0}^{m – 1}nums[i]$ 为缺失数值之和。

依据补全后数值各不相同可知，两者必不可能同时位于 $t = \left \lfloor \frac{cur}{2} \right \rfloor$ 的同一侧（偏大、偏小或数值反复），因而咱们能够计算 $[1, t]$ 范畴内的实践总和与理论总和之间的差值来确定其一（将问题转换为求解缺失一值），再联合缺失两值之和 $sum$ 算得答案。

Java 代码：

class Solution {public int[] missingTwo(int[] nums) {int n = nums.length + 2, cur = n * (1 + n) / 2;
        for (int x : nums) cur -= x;
        int sum = cur, t = cur / 2;
        cur = t * (1 + t) / 2;
        for (int x : nums) {if (x <= t) cur -= x;
        }
        return new int[]{cur, sum - cur};
    }
}

TypeScript 代码：

function missingTwo(nums: number[]): number[] {let n = nums.length + 2, cur = Math.floor(n * (1 + n) / 2)
    for (let x of nums) cur -= x
    let sum = cur, t = Math.floor(cur / 2)
    cur = Math.floor(t * (1 + t) / 2)
    for (let x of nums) {if (x <= t) cur -= x
    }
    return [cur, sum - cur]
};

Python 代码：

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        n = len(nums) + 2
        cur = n * (1 + n) // 2 - sum(nums)
        tot, t = cur, cur // 2
        cur = t * (1 + t) // 2 - sum([x for x in nums if x <= t])
        return [cur, tot - cur]

工夫复杂度：$O(n)$
空间复杂度：$O(1)$

这是咱们「刷穿 LeetCode」系列文章的第 No. 面试题 17.19 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的合集新基地 🎉🎉

本文由 mdnice 多平台公布

关于后端:面试题-1719-消失的两个数字-简单数学运用题

题目形容

数学

最初