Проблема с гайками и болтами (проблема с замком и ключом) с использованием Hashmap
Дан набор из n гаек разных размеров и n болтов разных размеров. Между гайками и болтами существует взаимное соответствие. Эффективно подбирайте гайки и болты.
Ограничение: сравнение гайки с другой гайкой или болта с другим болтом не допускается. Это означает, что гайку можно сравнивать только с болтом, а болт можно сравнивать только с гайкой, чтобы увидеть, какой из них больше или меньше.
Примеры:
Input : nuts[] = {"@", "#", "$", "%", "^", "&"} bolts[] = {"$", "%", "&", "^", "@", "#"} Output : Matched nuts and bolts are- $ % & ^ @ # $ % & ^ @ #
Другой способ задать эту проблему - дать ящик с замками и ключами, где один замок можно открыть одним ключом в ящике. Нам нужно подобрать пару.
Ниже мы обсудили решение на основе сортировки.
Проблема с гайками и болтами (проблема с замком и ключом) | Набор 1
В этом посте обсуждается подход, основанный на хэш-карте.
- Пройдите массив орехов и создайте хэш-карту
- Пройдитесь по массиву болтов и найдите его в хэш-карте.
- Если он найден в хэш-карте гаек, это означает, что для этой гайки существуют болты.
Реализация:
Временная сложность этого решения составляет O(n).
Вспомогательное пространство: O(n) , потому что используется хэш-карта
Эта статья предоставлена Нитешем Кумаром . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью с помощью write.geeksforgeeks.org или отправить ее по адресу review-team@geeksforgeeks.org. Посмотрите, как ваша статья появится на главной странице GeeksforGeeks, и помогите другим гикам