Сложность: 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⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число.
😎 Решение:
public class Solution {
public int MissingNumber(int[] nums) {
Array.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;
}
}Ставь 👍 и забирай 📚 Базу знаний