Sorting + scan — это типовой алгоритмический приём:
сначала сортируем данные,
а потом одним линейным проходом по отсортированному массиву что-то накапливаем, сравниваем или ищем.
То есть:
1. sorting → упорядочили элементы
2. scan → прошлись слева направо один раз
Здесь scan не значит “сканировать камерой”. В алгоритмах это обычно значит linear scan — линейный проход по массиву.
Например:
arr = [5, 1, 3, 2]
arr.sort() # [1, 2, 3, 5]
for x in arr: # scan
print(x)
Но смысл не просто “напечатать”. Смысл в том, что после сортировки рядом оказываются элементы, которые логически удобно сравнивать.
Например, найти ближайшую пару чисел:
arr = [10, 2, 14, 4, 7]
arr.sort() # [2, 4, 7, 10, 14]
best = float("inf")
for i in range(1, len(arr)):
best = min(best, arr[i] - arr[i - 1])
print(best) # 2
Почему это работает? Потому что после сортировки ближайшие числа обязательно будут стоять рядом. Не надо сравнивать все пары.
Без сортировки пришлось бы делать так:
сравнить каждый элемент с каждым → O(n²)
А с sorting + scan:
сортировка → O(n log n)
проход → O(n)
итого → O(n log n)
Ещё пример: объединение интервалов.
intervals = [(5, 7), (1, 3), (2, 4), (8, 10)]
intervals.sort() # [(1, 3), (2, 4), (5, 7), (8, 10)]
merged = []
for start, end in intervals:
if not merged or start > merged[-1][1]:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
print(merged) # [[1, 4], [5, 7], [8, 10]]
То есть sorting + scan — это когда ты сначала создаёшь порядок, а потом используешь этот порядок, чтобы не думать обо всех комбинациях.
Очень коротко:
sorting + scan = отсортировать + пройти один раз
Типичные задачи, где это встречается:
найти дубликаты
найти ближайшие элементы
слить интервалы
посчитать группы одинаковых элементов
проверить пересечения
найти максимальный разрыв
обработать события по времени
Например, для дубликатов:
arr = [3, 1, 5, 3, 2]
arr.sort() # [1, 2, 3, 3, 5]
for i in range(1, len(arr)):
if arr[i] == arr[i - 1]:
print("duplicate:", arr[i])
Главная идея: сортировка превращает хаос в структуру, а scan извлекает из этой структуры ответ одним проходом.
