Сложность: 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 {
function missingNumber($nums) {
sort($nums);
if ($nums[count($nums) - 1] != count($nums)) {
return count($nums);
} else if ($nums[0] != 0) {
return 0;
}
for ($i = 1; $i < count($nums); $i++) {
$expectedNum = $nums[$i - 1] + 1;
if ($nums[$i] != $expectedNum) {
return $expectedNum;
}
}
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний