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