Проблема с гайками и болтами (задача с замком и ключом) с использованием быстрой сортировки
Дан набор из n гаек разных размеров и n болтов разных размеров. Между гайками и болтами существует взаимное соответствие. Эффективно подбирайте гайки и болты.
Ограничение: сравнение гайки с другой гайкой или болта с другим болтом не допускается. Это означает, что гайку можно сравнивать только с болтом, а болт можно сравнивать только с гайкой, чтобы увидеть, какая из них больше или меньше.
Другой способ решить эту проблему — дать ящик с замками и ключами, где один замок можно открыть одним ключом в ящике. Нам нужно подобрать пару.
Путь грубой силы: начнем с первого болта и сравним его с каждой гайкой, пока не найдем совпадение. В худшем случае нам потребуется n сравнений. Выполнение этого для всех болтов дает нам сложность O (n ^ 2).
Способ быстрой сортировки: мы можем использовать технику быстрой сортировки, чтобы решить эту проблему. Мы представляем гайки и болты в массиве символов для понимания логики.
Орехи представлены в виде массива символов
charnuts[] = {'@', '#', '$', '%', '^', '&'}
Болты представлены в виде массива символов
болты char[] = {'$', '%', '&', '^', '@', '#'}
Этот алгоритм сначала выполняет разбиение, выбирая последний элемент массива болтов в качестве опорного, перестраивая массив гаек и возвращая индекс разделения «i», так что все гайки меньше, чем гайки [i], находятся слева, а все гайки больше. чем орехи [i] находятся с правой стороны. Затем, используя гайки [i], мы можем разделить массив болтов. Операции разбиения можно легко реализовать за O(n). Эта операция также делает массив гаек и болтов хорошо секционированным. Теперь мы применяем это разбиение рекурсивно к левому и правому подмассиву гаек и болтов.
Как мы относимся к разбиению на гайки и болты, так что общая временная сложность будет? (2*nlogn) = (nlogn) в среднем.
Здесь для простоты мы всегда выбирали последний элемент в качестве опорного. Мы также можем сделать рандомизированную быструю сортировку.
Ниже приведена реализация вышеупомянутой идеи:
Выход:
Matched nuts and bolts are : # $ % & @ ^ # $ % & @ ^
Временная сложность: O(N*logN), так как мы используем цикл для прохождения N раз в функции распределения, поэтому это стоит O(N) времени, и мы вызываем функцию распределения при каждом рекурсивном вызове функции matchPairs, которая стоит O( logN) раз, так как при рекурсивном вызове мы делим массив пополам. Где N — длина строки.
Вспомогательное пространство: O(logN)
Проблема с гайками и болтами (проблема с замком и ключом) | Набор 2 (хэш-карта)
Эта статья предоставлена Кумаром Гаутамом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.