Дан слайс целых неотрицательных чисел. Найдите минимальное неотрицательное
число, которого в слайсе нет (так называемый MEX).
// MissingMin возвращает минимальное x >= 0, которого нет в nums.
func MissingMin(nums []int) int
Примеры
[3, 0, 1] → 2
[1, 2, 3] → 0
[0, 1, 2] → 3
[0, 0, 1, 1] → 2
[] → 0
[5, 1000000000000] → 0
Ограничения
0 ≤ len(nums) ≤ 10⁶, 0 ≤ nums[i] ≤ 2⁶² — значения могут быть огромными.- Входной слайс не изменять.
- Ожидается O(n) по времени. Память под значения до максимального элемента
выделять нельзя: при
nums[i] ~ 10¹⁸ её не хватит.
Устно: какое наибольшее значение может принять ответ и почему?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.