Задача: найти недостающий элемент массива
2026-02-21 14:46 Diff
https://skillbox.ru/media/code/zadacha-nayti-nedostayushchiy-element-massiva/

#статьи

  • 20 дек 2022
  • 0

Задача: найти недостающий элемент массива

Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня ищем, какого элемента не хватает в массиве.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Дан массив целых чисел nums, в котором должны содержаться все числа из диапазона [0, n]. При этом n равно числу элементов в массиве, а значит, одного элемента всегда будет не хватать. Необходимо написать функцию, которая возвращает недостающее число из этого диапазона.

Ввод: nums = [3,0,1] Вывод: 2 Пояснение: n = 3, так как всего элементов в массиве три, поэтому все элементы находятся в диапазоне [0,3]. 2 — недостающий элемент. Ввод: nums = [0,1] Вывод: 2 Пояснение: n = 2, так как всего элементов в массиве два, поэтому все элементы находятся в диапазоне [0,2]. 2 — недостающий элемент. Ввод: nums = [9,6,4,2,3,5,7,0,1] Вывод: 8 Пояснение: n = 9, так как всего элементов в массиве девять, поэтому все элементы находятся в диапазоне [0,9]. 8 — недостающий элемент.

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

Нам нужно найти недостающее число. Из условия задачи мы знаем, что все элементы уникальные, то есть не повторяются. Поэтому если у нас есть, например, массив с размером в три элемента, то его элементы должны быть такими: [0, 1, 2, 3]. Однако размер у него 3, а значит, один из элементов всегда будет пропущен и массив будет выглядеть примерно так: [1, 0, 3].

Все элементы нашего массива всегда статичны, а значит, мы можем посчитать «идеальную» сумму всех элементов (в нашем случае от 1 до 3) и вычесть из неё сумму имеющихся в массиве чисел. Так мы найдём недостающее число:

public int missingNumber(int[] nums) { int realSum = 0; int sum = 0; for (int num : nums) { sum += num; } for (int i = 0; i <= nums.length; i++) { realSum += i; } return realSum - sum; }

Это решение можно немного оптимизировать и задействовать всего один цикл for:

public int missingNumber(int[] nums) { int rez = 0; int sum = 0; for (int i = 0; i < nums.length; i++) { sum += (i + 1); rez += nums[i]; } return sum - rez; }

Результаты

Временная сложность: O(n) — так как мы проходимся по всему массиву.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.

Научитесь: Профессия Java-разработчик + ИИ Узнать больше