Задача с собеседования в TCS
Дан массив nums, состоящий из различных чисел в диапазоне от 0 до n. Верните единственное число из диапазона, отсутствующее в массиве.
Follow up: можете ли вы реализовать решение с использованием лишь O(1) дополнительной памяти и временной сложностью O(n)?
Пример 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n=3, так как в массиве три числа; таким образом, все числа находятся в диапазоне [0, 3]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.
Пример 2:
Input: nums = [0,1]
Output: 2
Explanation: n=2, так как в массиве 2 числа; таким образом, все числа находятся в диапазоне [0, 2]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.
Пример 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n=9, так как в массиве 9 чисел; таким образом, все числа находятся в диапазоне [0, 9]. Число 8 отсутствует в этом диапазоне, поскольку его нет в массиве nums.
Ограничения:
n == nums.length
1
Дан массив nums, состоящий из различных чисел в диапазоне от 0 до n. Верните единственное число из диапазона, отсутствующее в массиве.
Follow up: можете ли вы реализовать решение с использованием лишь O(1) дополнительной памяти и временной сложностью O(n)?
Пример 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n=3, так как в массиве три числа; таким образом, все числа находятся в диапазоне [0, 3]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.
Пример 2:
Input: nums = [0,1]
Output: 2
Explanation: n=2, так как в массиве 2 числа; таким образом, все числа находятся в диапазоне [0, 2]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.
Пример 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n=9, так как в массиве 9 чисел; таким образом, все числа находятся в диапазоне [0, 9]. Число 8 отсутствует в этом диапазоне, поскольку его нет в массиве nums.
Ограничения:
n == nums.length
1