Поиск дублирующегося числа

Поиск дублирующегося числа

Это классическая задача, которая требует применения цикла Флойда (Floyds Cycle Detection Algorithm, он же алгоритм черепахи и зайца). Решение работает за O(n) времени и O(1) памяти.

Почему это сложно

Ограничения задачи делают наивные подходы невозможными:

• Set/Dict — требуют O(n) памяти
• Сортировка — модифицирует массив
• Маркировка — модифицирует массив

Ключевая идея: Связный список

Массив можно представить как связный список, где индекс — это следующий элемент:

Массив: [1, 3, 4, 2, 2]
Индексы: 0  1  2  3  4

Связный список:
0 → 1 → 3 → 2 → 4 → 2 → 4 → 2 → ...
          ↑_____________↓
          Цикл (дублик = 2)

Дублирующееся число создаёт цикл в этом списке, потому что несколько индексов ведут на одно число.

Алгоритм Флойда (Cycle Detection)

Шаг 1: Обнаруживаем наличие цикла

Используем двух «бегунов» — медленного (шаг 1) и быстрого (шаг 2):

def find_duplicate(nums):
    # Фаза 1: Обнаруживаем цикл
    slow = nums[0]
    fast = nums[0]
    
    # Медленный движется на 1 шаг, быстрый на 2
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        
        if slow == fast:  # Цикл найден
            break
    
    # Фаза 2: Находим начало цикла
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow

Почему это работает

Фаза 1: Обнаружение цикла

Когда в списке есть цикл, быстрый бегун всегда догонит медленного:

Массив: [1, 3, 4, 2, 2]

Шаг 0:
  slow = nums[0] = 1
  fast = nums[nums[0]] = nums[1] = 3

Шаг 1:
  slow = nums[1] = 3
  fast = nums[nums[3]] = nums[2] = 4

Шаг 2:
  slow = nums[3] = 2
  fast = nums[nums[4]] = nums[2] = 4

Шаг 3:
  slow = nums[2] = 4
  fast = nums[nums[4]] = nums[2] = 4  ← Встретились!

Они встречаются где-то в цикле.

Фаза 2: Начало цикла = Дублик

Математически доказано: расстояние от начала списка до начала цикла равно расстоянию от точки встречи до начала цикла. Поэтому:

1. Ставим одного бегуна в начало (nums[0])
2. Другой остаётся в точке встречи
3. Оба двигаются на 1 шаг за раз
4. Когда встречаются — это начало цикла (дублик)

Полная реализация

def find_duplicate(nums):
    """
    Находит дублирующееся число в массиве [1, n] с n+1 элементами.
    
    Сложность: O(n) время, O(1) память
    Алгоритм: Floyds Cycle Detection (черепаха и заяц)
    """
    # Фаза 1: Обнаруживаем цикл
    slow = nums[0]
    fast = nums[0]
    
    # Медленный: step 1, быстрый: step 2
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    # Фаза 2: Находим начало цикла
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow


# Тестирование
print(find_duplicate([1, 3, 4, 2, 2]))  # 2
print(find_duplicate([3, 1, 3, 4, 2]))  # 3
print(find_duplicate([2, 5, 9, 6, 4, 3, 7, 8, 1, 1]))  # 1
print(find_duplicate([1, 4, 4, 2, 4]))  # 4

Пошаговый пример

Массив: [3, 1, 3, 4, 2]

Фаза 1: Обнаружение цикла
  slow=3, fast=3
  slow=4, fast=4  (nums[nums[4]]=nums[2]=3, nums[3]=4)
  slow=2, fast=3  (nums[4]=2, nums[3]=4... хм, надо пересчитать)
  
Актуально:
  Начало: slow=nums[0]=3, fast=nums[0]=3
  Итер 1: slow=nums[3]=4, fast=nums[nums[3]]=nums[4]=2
  Итер 2: slow=nums[4]=2, fast=nums[nums[2]]=nums[3]=4
  Итер 3: slow=nums[2]=3, fast=nums[nums[4]]=nums[2]=3 ← Встреча!

Фаза 2: Начало цикла
  slow=nums[0]=3, fast=3
  Встреча? Нет
  slow=nums[3]=4, fast=nums[3]=4 ← Встреча!
  Результат: 4... Нет, это не правильно.
  
  На самом деле, нужно быть осторожнее с инициализацией.
  После фазы 1: slow и fast встретились в одной точке цикла.
  fast остаётся там, slow = nums[0]
  Идём по одному шагу, пока не встретимся.

Альтернативное объяснение (Binary Search)

Есть и другой способ — бинарный поиск за O(n log n), но с O(1) памятью:

def find_duplicate_binary_search(nums):
    """
    Бинарный поиск по значениям [1, n]
    """
    left, right = 1, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        # Сколько элементов <= mid?
        count = sum(1 for num in nums if num <= mid)
        
        if count > mid:
            # Дублик в [left, mid]
            right = mid
        else:
            # Дублик в [mid+1, right]
            left = mid + 1
    
    return left

print(find_duplicate_binary_search([1, 3, 4, 2, 2]))  # 2

Сравнение подходов

Cycle Detection — это элегантное решение, которое показывает глубокое понимание структур данных и алгоритмов.