javascript - 从未排序的数组中查找缺失的数字

Question

我找到了这个 JavaScript 算法练习:

问题:

从 1 到 100 的未排序数字数组中不包括一个数字，您将如何找到该数字？

作者给出的解决方案是:

function missingNumber(arr) {
    var n = arr.length + 1,
        sum = 0,
        expectedSum = n * (n + 1) / 2;

    for (var i = 0, len = arr.length; i < len; i++) {
        sum += arr[i];
    }

    return expectedSum - sum;
}

我想尝试做到这一点，这样您就可以找到多个缺失的数字。

我的解决方案:

var someArr = [2, 5, 3, 1, 4, 7, 10, 15]

function findMissingNumbers(arr) {
    var missingNumbersCount;
    var missingNumbers = [];
    arr.sort(function(a, b) {
        return a - b;
    })  
    for(var i = 0; i < arr.length; i++) {
        if(arr[i+1] - arr[i] != 1 && arr[i+1] != undefined) {
            missingNumbersCount = arr[i+1] - arr[i] - 1;
            for(j = 1; j <= missingNumbersCount; j++) {
                missingNumbers.push(arr[i] + j)
            }
        }
    }
    return missingNumbers
}

findMissingNumbers(someArr) // [6, 8, 9, 11, 12, 13, 14]

有更好的方法吗？它必须是 JavaScript，因为这是我正在练习的。

Answer 1

您可以在与输入数组中的值相对应的索引处使用具有 1 值的稀疏数组。然后，您可以创建另一个包含所有数字的数组(与稀疏数组的长度相同)，并仅保留与稀疏数组中值为 1 的索引相对应的那些值。

这将在 O(n) 时间内运行:

function findMissingNumbers(arr) {
    // Create sparse array with a 1 at each index equal to a value in the input.
    var sparse = arr.reduce((sparse, i) => (sparse[i]=1,sparse), []);
    // Create array 0..highest number, and retain only those values for which
    // the sparse array has nothing at that index (and eliminate the 0 value).
    return [...sparse.keys()].filter(i => i && !sparse[i]);
}

var someArr = [2, 5, 3, 1, 4, 7, 10, 15]
var result = findMissingNumbers(someArr);
console.log(result);

注意:这需要 EcmaScript2015 支持。