PrepBro
← Назад к вопросам

Поиск дубликатов в массиве

1.2 Junior🔥 191 комментариев
#Python Core

Условие

Дан массив чисел размера n, где все числа в диапазоне [1, n]. Некоторые числа могут повторяться. Найдите все дубликаты.

Требования: O(n) по времени, O(1) по дополнительной памяти.

Пример

find_duplicates([4, 3, 2, 7, 8, 2, 3, 1]) → [2, 3] find_duplicates([1, 1, 2]) → [1]

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Поиск дубликатов в массиве

Это классическая задача с ограничениями по памяти и времени. Даны числа в диапазоне [1, n] для массива размера n, что позволяет использовать сам массив как хеш-таблицу.

1. Наивное решение O(n) память

def find_duplicates_naive(nums: list[int]) -> list[int]:
    """Простое решение со множеством (O(n) дополнительная память)."""
    seen = set()
    duplicates = set()
    
    for num in nums:
        if num in seen:
            duplicates.add(num)
        else:
            seen.add(num)
    
    return sorted(list(duplicates))

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

Анализ:

  • Время: O(n)
  • Память: O(n) — дополнительное пространство для set
  • Проблема: НЕ удовлетворяет требованию O(1) памяти

2. Оптимальное решение — использование индексов (O(1) память)

Ключевая идея: использовать сам массив как хеш-таблицу.

Поскольку все числа в диапазоне [1, n], мы можем использовать индекс как ключ!

def find_duplicates_optimal(nums: list[int]) -> list[int]:
    """Оптимальное решение: O(n) время, O(1) память (без учёта выхода)."""
    duplicates = []
    
    for num in nums:
        # Берём абсолютное значение (на случай если число отрицательное)
        index = abs(num) - 1
        
        # Если число на позиции index уже отрицательное,
        # значит мы встретили это число второй раз
        if nums[index] < 0:
            duplicates.append(abs(num))
        else:
            # Отмечаем позицию как посещённую (делаем отрицательной)
            nums[index] = -nums[index]
    
    return duplicates

# Тестирование
arr1 = [4, 3, 2, 7, 8, 2, 3, 1]
print(find_duplicates_optimal(arr1))  # [2, 3]

arr2 = [1, 1, 2]
print(find_duplicates_optimal(arr2))  # [1]

Как это работает? Визуализация:

Массив: [4, 3, 2, 7, 8, 2, 3, 1]
Индекс:  0  1  2  3  4  5  6  7

Шаг 1: num=4
  index = abs(4) - 1 = 3
  nums[3] = 7 > 0, делаем nums[3] = -7
  Массив: [4, 3, 2, -7, 8, 2, 3, 1]

Шаг 2: num=3
  index = abs(3) - 1 = 2
  nums[2] = 2 > 0, делаем nums[2] = -2
  Массив: [4, 3, -2, -7, 8, 2, 3, 1]

Шаг 3: num=2
  index = abs(2) - 1 = 1
  nums[1] = 3 > 0, делаем nums[1] = -3
  Массив: [4, -3, -2, -7, 8, 2, 3, 1]

Шаг 4: num=7
  index = abs(7) - 1 = 6
  nums[6] = 3 > 0, делаем nums[6] = -3
  Массив: [4, -3, -2, -7, 8, 2, -3, 1]

Шаг 5: num=8
  index = abs(8) - 1 = 7
  nums[7] = 1 > 0, делаем nums[7] = -1
  Массив: [4, -3, -2, -7, 8, 2, -3, -1]

Шаг 6: num=2 (ДУБЛИКАТ!)
  index = abs(2) - 1 = 1
  nums[1] = -3 < 0 ✓ НАЙДЕН ДУБЛИКАТ!
  duplicates = [2]

Шаг 7: num=3 (ДУБЛИКАТ!)
  index = abs(3) - 1 = 2
  nums[2] = -2 < 0 ✓ НАЙДЕН ДУБЛИКАТ!
  duplicates = [2, 3]

Шаг 8: num=1
  index = abs(1) - 1 = 0
  nums[0] = 4 > 0, делаем nums[0] = -4
  Массив: [-4, -3, -2, -7, 8, 2, -3, -1]

Результат: [2, 3] ✓

Анализ сложности:

  • Время: O(n) — один проход по массиву
  • Память: O(1) — используем только переменные цикла
  • Предупреждение: Модифицирует исходный массив!

3. Если не можем модифицировать массив

def find_duplicates_non_destructive(nums: list[int]) -> list[int]:
    """Решение без модификации исходного массива."""
    nums_copy = nums[:]  # Копируем массив
    duplicates = []
    
    for num in nums_copy:
        index = abs(num) - 1
        
        if nums_copy[index] < 0:
            duplicates.append(abs(num))
        else:
            nums_copy[index] = -nums_copy[index]
    
    return duplicates

# Исходный массив не изменяется
arr = [4, 3, 2, 7, 8, 2, 3, 1]
print(find_duplicates_non_destructive(arr))  # [2, 3]
print(arr)  # [4, 3, 2, 7, 8, 2, 3, 1] — не изменился

4. Альтернатива: Floyd's Cycle Detection (для специального случая)

Если массив содержит ровно один дубликат и размер n, это становится задачей "Linked List Cycle":

def find_single_duplicate(nums: list[int]) -> int:
    """Найти единственный дубликат, остальные уникальны."""
    
    # Phase 1: Обнаружение цикла (быстрый и медленный указатели)
    slow = fast = nums[0]
    
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break  # Цикл найден
    
    # Phase 2: Поиск начала цикла
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow

# Работает для массива [1, 3, 4, 2, 2] → 2
print(find_single_duplicate([1, 3, 4, 2, 2]))  # 2

5. Полное решение с тестами

from typing import List

def find_duplicates(nums: List[int]) -> List[int]:
    """Найти все дубликаты за O(n) время и O(1) память."""
    if not nums:
        return []
    
    duplicates = set()  # Используем set чтобы избежать дублей в выводе
    
    for num in nums:
        index = abs(num) - 1
        
        # Проверяем, встречали ли мы это число
        if nums[index] < 0:
            duplicates.add(abs(num))
        else:
            # Отмечаем позицию как посещённую
            nums[index] = -nums[index]
    
    return sorted(list(duplicates))


# Полный набор тестов
import unittest

class TestFindDuplicates(unittest.TestCase):
    
    def test_basic_case(self):
        nums = [4, 3, 2, 7, 8, 2, 3, 1]
        result = find_duplicates(nums)
        self.assertEqual(result, [2, 3])
    
    def test_single_duplicate(self):
        nums = [1, 1, 2]
        result = find_duplicates(nums)
        self.assertEqual(result, [1])
    
    def test_multiple_duplicates(self):
        nums = [1, 2, 2, 3, 3, 3, 4]
        result = find_duplicates(nums)
        self.assertEqual(result, [2, 3])
    
    def test_all_duplicates(self):
        nums = [1, 1, 1, 2, 2]
        result = find_duplicates(nums)
        self.assertEqual(result, [1, 2])
    
    def test_no_duplicates(self):
        nums = [1, 2, 3, 4, 5]
        result = find_duplicates(nums)
        self.assertEqual(result, [])
    
    def test_empty_array(self):
        result = find_duplicates([])
        self.assertEqual(result, [])
    
    def test_single_element(self):
        nums = [1]
        result = find_duplicates(nums)
        self.assertEqual(result, [])
    
    def test_large_array(self):
        nums = list(range(1, 1001)) + [500, 750]
        result = find_duplicates(nums)
        self.assertEqual(result, [500, 750])

if __name__ == '__main__':
    unittest.main()

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

РешениеВремяПамятьМодифицируетСложность
С setO(n)O(n)НетПростое
С индексамиO(n)O(1)ДаСложное
Копия + индексыO(n)O(n)НетСреднее
Floyd's cycleO(n)O(1)ДаОчень сложное

7. Важные замечания

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

  1. Числа в диапазоне [1, n], индексы в диапазоне [0, n-1]
  2. Каждое число уникально映射 на позицию в массиве
  3. Если число встречается дважды, позиция будет посещена дважды
  4. Второе посещение (отрицательный флаг) указывает на дубликат

Предупреждения:

  • Решение с индексами изменяет исходный массив
  • Предполагается, что числа в диапазоне [1, n]
  • Не подходит для других диапазонов чисел

8. Вариант для диапазона [0, n-1]

def find_duplicates_zero_based(nums: List[int]) -> List[int]:
    """Для диапазона [0, n-1] вместо [1, n]."""
    duplicates = set()
    
    for num in nums:
        index = num  # Прямо используем как индекс
        
        if nums[index] < 0:
            duplicates.add(abs(num))
        else:
            nums[index] = -nums[index]
    
    return sorted(list(duplicates))

Вывод

Оптимальное решение использует сам массив как хеш-таблицу, отмечая посещённые позиции отрицательными числами. Это позволяет достичь:

  • O(n) по времени
  • O(1) по дополнительной памяти
  • Одного прохода по массиву

Это элегантное решение часто задают на собеседованиях, проверяя способность думать неординарно и использовать ограничения задачи.

Поиск дубликатов в массиве | PrepBro