Сложность: 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 {
func missingNumber(_ nums: [Int]) -> Int {
let sortedNums = nums.sorted()
if sortedNums.last != sortedNums.count {
return sortedNums.count
} else if sortedNums.first != 0 {
return 0
}
for i in 1..<sortedNums.count {
let expectedNum = sortedNums[i - 1] + 1
if sortedNums[i] != expectedNum {
return expectedNum
}
}
return -1
}
}Ставь 👍 и забирай 📚 Базу знаний