Сложность: medium
Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.
В массиве есть только одно повторяющееся число, верните это повторяющееся число.
Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.
Пример:
Input: nums = [1,3,4,2,2]
Output: 2
👨💻 Алгоритм:
1⃣Определение дубликата:
Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс.
Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла.
Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу.
2⃣Восстановление массива:
Пройдите по массиву и измените все отрицательные элементы обратно на положительные, чтобы восстановить исходное состояние массива.
3⃣Возврат результата:
Верните найденный дубликат.
😎 Решение:
func findDuplicate(nums []int) int {
duplicate := -1
for i := 0; i < len(nums); i++ {
cur := abs(nums[i])
if nums[cur] < 0 {
duplicate = cur
break
}
nums[cur] *= -1
}
for i := 0; i < len(nums); i++ {
nums[i] = abs(nums[i])
}
return duplicate
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Ставь 👍 и забирай 📚 Базу знаний