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