Циклическая сортировка — это алгоритм сортировки на месте. Этот шаблон описывает интересный подход к решению проблем, связанных с массивами, содержащими числа в заданном диапазоне.
- Он оптимален с точки зрения количества операций записи в память.
- Он основан на идее, что сортируемый массив можно разбить на циклы. Циклы можно представить в виде графика.
Основная идея:данный элемент 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 для практики: