Как найти дубликат среди роботов и не быть разоблачённым
🎯 Цель миссии: Найти двойника!
Так, представьте, что вы тайный агент и вам нужно найти "подкаблучника" в армии роботов. Все роботы выстроены в ряд и у каждого есть уникальный идентификатор (ID). Но ой-вей! Один из них — двойник! Ваша задача — найти этого проклятого двойника, не нарушив при этом правила времени и пространства. 🕵️♂️💡
Задача: Найти дубликат в массиве. Массив состоит из n+1 элементов, где каждый элемент ∈[1,n].
📚 Что нового я узнаю
- Как работают двухуказательные методы
- Как быстро найти дубликат в массиве
🎭 Шаг 1: Введение в "Метод двойного агента"
Итак, один из наших агентов, работающих внутри кода, предложил метод двух указателей, или "метод двойного агента". Один указатель двигается быстро, другой медленно. Если быстрый догоняет медленного — Bingo! У нас есть двойник!
⚡️Почему это быстро? Потому что каждый указатель проходит по массиву только один раз.
🛠 Шаг 2: Пишем код, как пишут шпионы шифры
# Инициализация двух указателей
slow = nums[0]
fast = nums[0]
Тут мы создаем двух агентов: один "медленный", другой "быстрый". Все они начинают свою миссию с первого элемента массива (или первого робота в армии, если уж на то пошло).
🏎 Шаг 3: Пересечение указателей, или "Точка встречи"
# Находим пересечение
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
В этом цикле наши агенты двигаются вглубь массива: медленный на одну позицию за итерацию, быстрый — на две. Как только они встречаются, это означает, что мы нашли цикл и, соответственно, двойника.
🕵️♂️ Финальный код миссии
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# Инициализация двух указателей
slow = nums[0]
fast = nums[0]
# Находим пересечение
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Находим вход в цикл
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
🚀 Асимптотика
Асимптотика этого метода — O(n). Потому что каждый указатель проходит по массиву только один раз.
🎉 Анекдот
Знаете, почему роботы никогда не станут тайными агентами? Потому что их нельзя научить пить мартини, разбавленный, но не взболтанный!
Сохраните мир и код на этой неделе, агенты! 🕵️♂️🎉