Циклическая сортировка — это алгоритм сортировки на месте. Этот шаблон описывает интересный подход к решению проблем, связанных с массивами, содержащими числа в заданном диапазоне.

  • Он оптимален с точки зрения количества операций записи в память.
  • Он основан на идее, что сортируемый массив можно разбить на циклы. Циклы можно представить в виде графика.

Основная идея:данный элемент a, мы можем найти индекс, под которым он будет встречаться в отсортированном списке, просто подсчитав количество элементов во всем списке, которые меньше, чем a.

Я нашел это видео на YouTube чрезвычайно полезным, поэтому я хотел бы попросить вас сначала посмотреть его, прежде чем решать какую-либо задачу.

Циклическая сортировка — вопросы интервью Amazon, Google, Microsoft

Получить репозиторий этих примеров:

https://github.com/LuisSalas94/Cyclic-Sort-Pattern-Article

Пример 01:

Постановка задачи: циклическая сортировка

Нам дан массив, содержащий n объектов. Каждому объекту при создании был присвоен уникальный номер в диапазоне от 1 до n в зависимости от последовательности их создания. Это означает, что объект с порядковым номером 3 был создан непосредственно перед объектом с порядковым номером 4. Напишите функцию для сортировки объектов. на месте в порядковом номере их создания за O(n) и без использования дополнительного пробела.

Ввод: [2, 6, 4, 3, 1, 5]

Вывод: [1, 2, 3, 4 , 5, 6]

Объяснение. Как мы знаем, входной массив содержит числа от 1 до n. Мы можем использовать этот факт для создания эффективного способа сортировки чисел. Поскольку все числа уникальны, мы можем попробовать разместить каждое число на правильном месте, поместив 1 на индекс «0», поместив 2 на индекс «1» и так далее. Чтобы поместить число в его правильный индекс, нам сначала нужно найти это число. Что, если мы перебираем массив по одному числу за раз, и если текущее число, которое мы итерируем, не находится в правильном индексе, мы заменяем его числом с его правильным индексом. Таким образом, мы будем повторять все числа и размещать их в правильных индексах.

Пример 02:

Постановка задачи: найти недостающее число — 268. Недостающее число (LeetCode)

Нам дан массив, содержащий n различных чисел, взятых из диапазона от 0 до n. Поскольку в массиве всего n чисел из общего числа n+1, найдите недостающее число.

Ввод: [4, 0, 3, 1]

Вывод: [2]

Объяснение.Эта проблема связана с шаблоном циклической сортировки. Поскольку входной массив содержит уникальные числа в диапазоне от 0 до n, мы можем использовать аналогичную стратегию, описанную в циклической сортировке, чтобы поместить числа в их правильный индекс. Когда у нас есть каждое число на своем правильном месте, мы можем перебрать массив, чтобы найти индекс, который не имеет правильного числа, и этот индекс будет нашим отсутствующим числом.

Пример 03:

Постановка задачи: найти все отсутствующие числа — 448. Найти все отсутствующие числа в массиве

Нам дан несортированный массив, содержащий числа, взятые из диапазона от 1 до «n». Массив может иметь дубликаты, что означает, что некоторые числа будут отсутствовать. Найдите все эти недостающие числа.

Ввод: [2, 3, 1, 8, 2, 3, 5, 1]

Вывод: 4, 6, 7

Объяснение. В массиве должны быть все числа от 1 до 8, так как дубликаты 4, 6 и 7 отсутствуют.

Дополнительные задачи LeetCode для практики: