0 added
0 removed
Original
2026-01-01
Modified
2026-02-21
1
<p><a>#статьи</a></p>
1
<p><a>#статьи</a></p>
2
<ul><li>20 дек 2022</li>
2
<ul><li>20 дек 2022</li>
3
<li>0</li>
3
<li>0</li>
4
</ul><h2>Задача: найти недостающий элемент массива</h2>
4
</ul><h2>Задача: найти недостающий элемент массива</h2>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня ищем, какого элемента не хватает в массиве.</p>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня ищем, какого элемента не хватает в массиве.</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
8
<p><strong>Условие.</strong>Дан массив целых чисел nums, в котором должны содержаться все числа из диапазона [0, n]. При этом n равно числу элементов в массиве, а значит, одного элемента всегда будет не хватать. Необходимо написать функцию, которая возвращает недостающее число из этого диапазона.</p>
8
<p><strong>Условие.</strong>Дан массив целых чисел nums, в котором должны содержаться все числа из диапазона [0, n]. При этом n равно числу элементов в массиве, а значит, одного элемента всегда будет не хватать. Необходимо написать функцию, которая возвращает недостающее число из этого диапазона.</p>
9
Ввод: 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 - недостающий элемент.<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из телеграм-канала Сергея<a>Cracking code interview</a>.</p>
9
Ввод: 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 - недостающий элемент.<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из телеграм-канала Сергея<a>Cracking code interview</a>.</p>
10
<p><strong>Решение</strong></p>
10
<p><strong>Решение</strong></p>
11
<p>Нам нужно найти недостающее число. Из условия задачи мы знаем, что все элементы уникальные, то есть не повторяются. Поэтому если у нас есть, например, массив с размером в три элемента, то его элементы должны быть такими: [0, 1, 2, 3]. Однако размер у него 3, а значит, один из элементов всегда будет пропущен и массив будет выглядеть примерно так: [1, 0, 3].</p>
11
<p>Нам нужно найти недостающее число. Из условия задачи мы знаем, что все элементы уникальные, то есть не повторяются. Поэтому если у нас есть, например, массив с размером в три элемента, то его элементы должны быть такими: [0, 1, 2, 3]. Однако размер у него 3, а значит, один из элементов всегда будет пропущен и массив будет выглядеть примерно так: [1, 0, 3].</p>
12
<p>Все элементы нашего массива всегда статичны, а значит, мы можем посчитать "идеальную" сумму всех элементов (в нашем случае от 1 до 3) и вычесть из неё сумму имеющихся в массиве чисел. Так мы найдём недостающее число:</p>
12
<p>Все элементы нашего массива всегда статичны, а значит, мы можем посчитать "идеальную" сумму всех элементов (в нашем случае от 1 до 3) и вычесть из неё сумму имеющихся в массиве чисел. Так мы найдём недостающее число:</p>
13
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; }<p>Это решение можно немного оптимизировать и задействовать всего один цикл for:</p>
13
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; }<p>Это решение можно немного оптимизировать и задействовать всего один цикл for:</p>
14
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; }<p><strong>Результаты</strong></p>
14
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; }<p><strong>Результаты</strong></p>
15
<p><strong>Временная сложность:</strong>O(n) - так как мы проходимся по всему массиву.</p>
15
<p><strong>Временная сложность:</strong>O(n) - так как мы проходимся по всему массиву.</p>
16
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти.</p>
16
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти.</p>
17
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>
17
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>