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

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 支持。