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

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，因为我正在练习它。

- Jaeeun Lee

---

可能是与 Easy interview question got harder: given numbers 1..100, find the missing number(s) 相关的重复问题。 - Paul Hankin

@PaulHankin 我认为这篇帖子并不特指JavaScript。 - Jaeeun Lee

在伪代码中，有几种出色的解决方案可用于解决这个问题。如果你的问题是“有什么更好的算法来解决这个问题？”，那么它就是一个重复的问题。如果你的问题是“我知道这些算法，但有人可以帮我将它们翻译成JavaScript吗？”，那么这个问题就不属于主题。 - Paul Hankin

@PaulHankin 我认为这不是离题的 http://stackoverflow.com/help/on-topic - Jaeeun Lee

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);

NB: 这需要 EcmaScript2015 支持。

- trincot

Answer 2

这个问题的最简单解决方案是：

miss = (arr) => {
    let missArr=[];
    let l = Math.max(...arr);
    let startsWithZero = arr.indexOf(0) > -1 ? 0 : 1;
    for(i = startsWithZero; i < l; i++) {
        if(arr.indexOf(i) < 0) {
            missArr.push(i);
        }
    }
    return missArr;
}
miss([3,4,1,2,6,8,12]);

- satyanarayan mishra

---

我不会循环到maxNumber，因为我们知道它存在于数组中。 - satyanarayan mishra

Answer 3

像这样的代码可以实现您想要的功能。

    var X = [2, 5, 3, 1, 4, 7, 10, 15]; // Array of numbers
    var N = Array.from(Array(Math.max.apply(Math, X)).keys()); //Generate number array using the largest int from X
    
    Array.prototype.diff = function(a) {
        return this.filter(function(i) {return a.indexOf(i) < 0;}); //Return the difference
    }; 
    console.log(N.diff(X));

- Mike

---

为什么需要创建N数组--这不是一种将i范围在0 ... Max(X)之间的复杂方式吗？indexOf调用不会导致代码花费O(n^2)的时间吗？ - Paul Hankin

Answer 4

我的解决方案使用了与trincot's answer相同的逻辑

时间复杂度为O(n)

const check_miss = (n) => {
  let temp = Array(Math.max(...n)).fill(0);

  n.forEach((item) => (temp[item] = 1));

  const missing_items = temp
    .map((item, index) => (item === 0 ? index : -1))
    .filter((item) => item !== -1);

  console.log(missing_items);
};

n = [5, 4, 2, 1, 10, 20, 0];
check_miss(n);

- Abhiswain

Answer 5

解决在未排序的数组或包含重复值的数组中找到缺失数字的问题。

Array.prototype.max = function() {
  return Math.max.apply(null, this);
};

var array1 = [1, 3, 4, 7, 9];
var n = array1.length;
var totalElements = array1.max(); // Total count including missing numbers. Can use max 
var d = new Uint8Array(totalElements)

for(let i=0; i<n; i++){
 d[array1[i]-1] = 1;
}
var outputArray = [];
for(let i=0; i<totalElements; i++) {
 if(d[i] == 0) {
   outputArray.push(i+1)
 }
}
console.log(outputArray.toString());

- Nandakumar

Answer 6

我认为在单个缺失数字的情况下，最好的方法是使用求和方法而不需要任何迭代。

const arr=[1-100];


let total=n*(n+1)/2;


let totalarray=array.reduce((t,i)=>t+i);

console.log(total-totalarray);

- Parijat

---

“n” 会被评估为什么？ - Caleb Jay

可能会有多个遗漏的数字。 - Yola

Answer 7

Option 1: 
1. create a binary array
2. iterate over input array and for each element mark binary array true.
3. iterate over binary array and find out numbers of false.

Time complexity = O(N)
Space complexity = N

Option 2:
Sort input array O(nLogn)
iterate over sorted array and identify missing number a[i+1]-a[i] > 0
O(n)

total time complexity = O(nlogn) + O(n)

- Vikram Singh

Answer 8

你可以尝试这个：

let missingNum= (n) => {
    return n
        .sort((a, b) => a - b)
        .reduce((r, v, i, a) =>
            (l => r.concat(Array.from({ length: v - l - 1 }, _ => ++l)))(a[i - 1]),
            []
        )
}

console.log(missingNum([1,2,3,4,10]));

- Sudhir Kumar