Поиск дубликата в массиве
Medium
Массив длины
n+1 содержит числа из диапазона 1..n; ровно одно число повторяется (остальные встречаются по одному разу). Найдите это повторяющееся число. Доп. память ограничена константой: нельзя просто сложить все значения в множество.Примеры:
Вход:
[1, 3, 4, 2, 2]
Выход:
2
Объяснение: В [1,3,4,2,2] дважды встречается 2 → ответ 2.
Вход:
[3, 1, 3, 4, 2]
Выход:
3
Объяснение: В [3,1,3,4,2] дважды встречается 3 → ответ 3.
Вход:
[1, 1]
Выход:
1
Объяснение: Массив [1,1] при n=1: повтор — 1.
Ограничения:
2 <= n <= 100000
nums.length == n + 1
1 <= nums[i] <= n
Все числа от 1 до n встречаются хотя бы один раз, кроме одного, который встречается дважды
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!