Найти отсутствующее число в массиве

@sozdatel · Регистрация: 20.08.2016

Студворк — интернет-сервис помощи студентам

Вам предоставляется несортированный массив, содержащий все целые числа от 0 до 100 включительно. Однако одного номера не хватает. Напишите функцию, чтобы найти и вернуть это число.

JavaScript
1
2
3
4
5
6
7
function missingNo(nums) {
  for (let i = 0; i < nums.length; i++) {
    if (!nums.includes(nums[i])) {
      return nums[i];
    }
  }
}

Почему код не работает? Где ошибка?

@mr_dramm · 13.10.2021, 22:20

Потому что вы ищите цифры которые уже есть в массиве

@Egor.S · 13.10.2021, 22:32

думаю как-то так нужно решать эту задачу

JavaScript
1
2
3
4
5
6
7
function findLostNum(nums){
    const expectedSum = 5050; // (100(100 + 1))/2
    const sum = nums.reduce((prev, current) => {
        return prev + current;
    }, 0)
   return expectedSum - sum;
}

@sozdatel · 13.10.2021, 22:44 **[ТС]**

Egor.S, Спасибо, конечно, но я всё ещё не понял, где у меня ошибка.

mr_dramm, почему?

JavaScript
1
!nums.includes(nums[i])

@NTHing · 13.10.2021, 23:03

JavaScript
1
!nums.includes(nums[i])

Это условие вычисляется как false, поэтому функция ничего не возвращает.

@sozdatel · 13.10.2021, 23:11 **[ТС]**

NTHing, не понимаю,

JavaScript
1
2
3
4
5
6
7
function missingNo(nums) {
  for (let i = 0; i < nums.length; i++) {
    if (!nums.includes(nums[i])) {
      return nums[i];
    }
  }
}

цикл проходит по всем числам в массиве, и условие для всех кроме одного вычисляется как false, потому что массив содержит эти числа, но одно число, отсутствующее в массиве, должно подходить, и функция его должна возвращать.

@NTHing · 13.10.2021, 23:15

Наводящий вопрос... Число, которое отсутствует в массиве, оно где? Программа про это число знает?

@sozdatel · 13.10.2021, 23:36 **[ТС]**

NTHing, только сейчас примерно понял, где ошибка. Я написал код сначала, проверяющий каждый элемент массива, есть ли он в массиве. Естественно, он есть.)) Посмотрев решение в ответах, переделал код,

JavaScript
1
2
3
4
5
6
7
function missingNo(nums) {
  for (i = 0; i<= 100; i++) {
    if(!nums.includes(i)) {
      return i;
    }
  }
}

Заработало.

KingdaKa · 14.10.2021, 00:47

Вообще заставлять интерпретатор проходиться по массиву 100 раз в поисках нужного значения по 100 раз (всего 10 тыс сравнений!) - это жуть

В данном случае массив надо сначала отсортировать, а потом уже искать выпавшее значение т.к. оно неизвестно.
Алгоритм можно еще минимум в 2 раза ускорить, но это морока, поэтому вот простой вариант:

JavaScript
1
2
3
  let source = [13, 11, 2, 4, 3, 6, 7, 5, 9, 10, 0, 12, 1]; // нет 8
  let res = source.sort((a, b) => a - b).find((value, index) => value != index) - 1;
  console.log(res); // => 8

Есть вариант без сортировки, кстати, но это не сегодня ужо...

Профэссоры, поправляйте, если я неправ

@Balanaar · 14.10.2021, 00:53

KingdaKa, согласен, квадратичная сложность у ТСа это многовато... Но если уж оптимизировать до конца, то самый быстрый вариант у Egor.S. Вряд ли можно сделать быстрее.

KingdaKa · 14.10.2021, 00:55

Есть вариант без сортировки, кстати, это будет еще быстрее... может автор напишет?

@Balanaar · 14.10.2021, 00:59

Сообщение от KingdaKa

может автор напишет?

А может вы?

KingdaKa · 14.10.2021, 05:35

JavaScript
1
2
3
4
5
6
7
  "use strict";
  // Массив от 0 до 19 - 20 значений макс
  let source = [13, 4, 3, 6, 7, 5, 9, 10, 0, 12, 1, 14, 15, 16, 18, 19] // нет 2 8 11 17
  
  let target = Array(20).fill(true) // Заполняется существующими значениями (значение = его индексу)
  source.forEach((e) => delete target[e])
  target.forEach((e,k) => console.log(k)) // Печать отсутствующих значений

Профэссоры, как быстрее/короче? )))

@Balanaar · 14.10.2021, 09:51

Сообщение от KingdaKa

как быстрее

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]; // Пропущено 60
 
function findLostNumEgorS(nums){
  const expectedSum = 5050;
  const sum = nums.reduce((prev, current) => {
    return prev + current;
  }, 0)
  return expectedSum - sum;
}
 
function findLostNumKingdaKa(source){
  let target = Array(101).fill(true);
  source.forEach((e) => delete target[e]);
  for (let i = 0; i < target.length; i++) {
    if (target[i] !== undefined) return i;
  }
}
 
let startTime = performance.now();
for (let i = 0; i < 10000; i++) {
  findLostNumEgorS(nums);
}
console.log(performance.now() - startTime); // 8.7
startTime = performance.now();
for (let i = 0; i < 10000; i++) {
  findLostNumKingdaKa(nums);
}
console.log(performance.now() - startTime); // 89.6

@NTHing · 14.10.2021, 10:32

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
 
console.time('time')
function findLostNumEgorS(nums){
    const expectedSum = 5050;
    const sum = nums.reduce((prev, current) => {
        return prev + current;
    }, 0)
    return expectedSum - sum;
}
 
for (let i = 0; i < 10000; i++) {
    findLostNumEgorS(nums);
}
console.timeEnd('time')
 
console.time('time')
function findLostNumKingdaKa(source){
    let target = Array(101).fill(true);
    source.forEach((e) => delete target[e]);
    for (let i = 0; i < target.length; i++) {
        if (target[i] !== undefined) return i;
    }
}
 
for (let i = 0; i < 10000; i++) {
    findLostNumKingdaKa(nums)
}
console.timeEnd('time')

KingdaKa · 14.10.2021, 11:07

Граждане, вы вообще поняли что сравниваете-то?

Добавлено через 6 минут
То, что решение моего тёзки быстрее ясно и без сравнения, что и видно на тесте:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
  "use strict";
  
  const nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
 
console.time('time')
function findLostNumEgorS(nums){
    const expectedSum = 5050;
    const sum = nums.reduce((prev, current) => {
        return prev + current;
    }, 0)
    return expectedSum - sum;
}
 
for (let i = 0; i < 10000; i++) {
    findLostNumEgorS(nums);
}
console.timeEnd('time')
 
console.time('time')
function findLostNumKingdaKa(source){
    let res = source.sort((a, b) => a - b).find((value, index) => value != index) - 1;
    return res;
}
 
for (let i = 0; i < 10000; i++) {
    findLostNumKingdaKa(nums)
}
console.timeEnd('time')

time: 26 ms
time: 69 ms

Но смысл задачи уже поменялся

@NTHing · 14.10.2021, 11:12

Граждане, вы вообще поняли что сравниваете-то?

Я нет. Я за другими повторяю. Так легче.

@Balanaar · 14.10.2021, 11:17

Сообщение от KingdaKa

Граждане, вы вообще поняли что сравниваете-то?

Да.

Сообщение от KingdaKa

это будет еще быстрее...

Быстрее, чем что? Фраза следует сразу после моего поста о скорости работы алгоритма Egor.S. У меня было полное право толковать ваше сообщение в пользу заявления о том, что вы можете написать алгоритм быстрее обозначенного выше, раз уж вы не уточнили.
У нас в программировании всё строго: избегайте двоякого толкования. А раз уж избежать его не удалось, спокойно уточните, что вы имели в виду.

KingdaKa · 14.10.2021, 11:27

Сообщение от NTHing

Я нет. Я за другими повторяю. Так легче.

Иногда так правильнее

Выше я сделал сравнение как надо.

Кстати, я тоже посидел посравнивал кое-что. И как и ожидал выяснилось, что некоторые методы Array работают непростительно медленно. Может быть кто-то уже на этой планете всё сравнил и выложил табличку, коллеги?

Добавлено через 6 минут

Сообщение от Balanaar

Быстрее, чем что? Фраза следует сразу после моего поста о скорости работы алгоритма Egor.S.

Следует после, но к нему уже не относится

Я выложил другой скрипт для другого поиска, что видно в его комментариях.
Правда при редактировании случайно стёр пояснение над ним, вот это прокольчик, да, но двойного толкования всё-таки не вносит.

@Tavashi · 14.10.2021, 12:19

Сообщение от KingdaKa

Есть вариант без сортировки

С сортировкой для значений Z+ можно тоже сделать за линейное время, но этот способ все равно не будет быстрее способа с вычислением итоговой суммы.

Новые блоги и статьи Все статьи Все блоги /
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .

@mr_dramm Молодой техлид) 1818 / 1056 / 329 Регистрация: 17.07.2021 Сообщений: 2,147 Записей в блоге: 14
	13.10.2021, 22:20
	Потому что вы ищите цифры которые уже есть в массиве 0

@NTHing 1782 / 963 / 388 Регистрация: 26.11.2014 Сообщений: 1,966 Записей в блоге: 1
	13.10.2021, 23:15
	Наводящий вопрос... Число, которое отсутствует в массиве, оно где? Программа про это число знает? 2

@Balanaar 2463 / 1769 / 625 Регистрация: 11.07.2016 Сообщений: 4,067
	14.10.2021, 00:53
	KingdaKa, согласен, квадратичная сложность у ТСа это многовато... Но если уж оптимизировать до конца, то самый быстрый вариант у Egor.S. Вряд ли можно сделать быстрее. 0

KingdaKa 1306 / 781 / 190 Регистрация: 19.09.2020 Сообщений: 1,993
	14.10.2021, 00:55
	Есть вариант без сортировки, кстати, это будет еще быстрее... может автор напишет? 0