Сложность: easy
Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.
Пример:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
👨💻 Алгоритм:
1️⃣Сначала отсортируйте массив nums.
2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.
3️⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число.
😎 Решение:
class Solution:
def missingNumber(self, nums):
nums.sort()
if nums[-1] != len(nums):
return len(nums)
elif nums[0] != 0:
return 0
for i in range(1, len(nums)):
expected_num = nums[i - 1] + 1
if nums[i] != expected_num:
return expected_num
return -1
Ставь 👍 и забирай 📚 Базу знаний