Найти отсутствующее число в последовательности / множестве натуральных чисел

Question

У меня задача взять несортированный массив уникальных номеров от 1 до n и вывести числа, которые отсутствуют в этом диапазоне.

В конце задания написано: В массиве ни одно число не пропущено, или отсутствует ровно одно число. Можете найти его за O(N) времени? Подсказка: Можно использовать «Умную формулу».

Я полез в интернет посмотреть что за O(N) time, и оказалось это Временная сложность алгоритма, но я не понял как его реализовать.

PS: у меня если при итерации ничего не произошло должно вывести undefined

function missing(arr) {
    arr.sort((a, b) => { return a - b })

    let missingNum = []

    for(let i = 1; i < Math.max.apply(null, arr); i++) {
        let searched = arr.includes(i)

        if(searched !== false) {
            continue
        }

        missingNum.push(i)
    }

    if(missingNum.length === 0) {
        return undefined
    }

    return missingNum.join(', ')
}

console.log(missing([]))
console.log(missing([1, 4, 3]))
console.log(missing([2, 3, 4]))
console.log(missing([5, 1, 4, 2, 70]))
console.log(missing([1, 2, 3, 4]))

Answer 1

function missing(arr) {
  let all = [];
  all.length = arr.length? Math.max.apply(null, arr) : 0;
  for (let i = 0; i < all.length; i++)
    all[i] = i + 1;
  arr.forEach(i => all[i - 1] = -1);
  let missingNum = all.filter(i => i != -1);

  return missingNum.length ? missingNum.join(', ') : undefined;
}

console.log(missing([]))
console.log(missing([1, 4, 3]))
console.log(missing([2, 3, 4]))
console.log(missing([5, 1, 4, 2, 70]))
console.log(missing([1, 2, 3, 4]))

Answer 2

"Clever formula":

(n + 1) * n / 2

БЛОГ НА HUSL

Найти отсутствующее число в последовательности / множестве натуральных чисел

Ответы (2 шт):