从所有数字 1-n 的数组中找到 2 个被移除的数字

Question

面试时被问到这个问题：

从所有数字 1...n 的数组中找到 2 个被移除的数字。数组顺序是随机的 并且 不允许使用哈希图。

当我毫无头绪时，面试官给出了以下提示：

• 用 x 和 y 标记 2 个数字...（但我不知道该怎么做）
• 也许可以以某种方式使用总和？

最后我没有被告知正确的解决方案，我仍然没有线索。

当然，O(nlogn) 算法很简单，但挑战要求 O(n) 时间复杂度。

由于不允许使用哈希图/哈希集，我不知道如何解决这个问题。我的意思是，没有他们这怎么可能？

我们怎样才能在 O(n) 时间内找到两个缺失的数字？

Answer 1

您可以计算给定数字的总和和平方和，并将其与如果数组还包含两个缺失值 𝑥 和 𝑦 时的总和进行比较。

这给你两个方程：

• 𝑥 + 𝑦 = 𝑞
• 𝑥² + 𝑦² = 𝑝

其中 𝑞 是“预期”总和与实际总和之间的差值，𝑝 是预期平方和与实际平方和的差值。

代入𝑦，上式可改写为：

• 2𝑥² − 2𝑞𝑥 + 𝑞²−𝑝 = 0

该方程的两个解是 𝑥 和 𝑦 的值：

• 𝑥 = [𝑞 ± √(2𝑝 − 𝑞²)] / 2

这是 JavaScript 中的一个实现，其中从 1 到 20 的序列中删除两个随机数，并且算法检索缺失的值（因为该算法不使用输入的顺序，所以我没有费心去洗牌）输入）：

function createInput(n) {
    const arr = [...Array(n+1).keys()]; // {0,1,...,n}
    arr.shift(); // Remove 0 => {1,...,n}
    for (let removals = 1; removals <= 2; removals++) {
        const i = Math.floor(Math.random() * arr.length);
        arr.splice(i, 1); // Remove random element
    }
    return arr;
}

function findXY(arr) {
    const n = arr.length + 2;
    // Expected sum and sumOfSquares
    let sum = n * (n + 1) / 2;
    let sumSquares = sum * (2 * n + 1) / 3;
    // Subtract the actual sums
    for (let i = 0; i < arr.length; i++) {
        sum -= arr[i];
        sumSquares -= arr[i] * arr[i];
    }
    // Solution to quadratic equation
    const x = (sum - Math.sqrt(2 * sumSquares - sum * sum)) / 2;
    return [x, sum - x];
}

for (let run = 1; run <= 4; run++) {
    const arr = createInput(20);
    console.log("input  : ", ...arr);
    console.log("missing: ", ...findXY(arr));
}