Проблема с гайками и болтами (проблема с замком и ключом) с использованием Hashmap

Опубликовано: 14 Января, 2023

Дан набор из n гаек разных размеров и n болтов разных размеров. Между гайками и болтами существует взаимное соответствие. Эффективно подбирайте гайки и болты.
Ограничение: сравнение гайки с другой гайкой или болта с другим болтом не допускается. Это означает, что гайку можно сравнивать только с болтом, а болт можно сравнивать только с гайкой, чтобы увидеть, какой из них больше или меньше.

Примеры:

Input : nuts[] = {"@", "#", "$", "%", "^", "&"}
        bolts[] = {"$", "%", "&", "^", "@", "#"}
Output : Matched nuts and bolts are-
        $ % & ^ @ # 
        $ % & ^ @ #

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

Ниже мы обсудили решение на основе сортировки.
Проблема с гайками и болтами (проблема с замком и ключом) | Набор 1

В этом посте обсуждается подход, основанный на хэш-карте.

  1. Пройдите массив орехов и создайте хэш-карту
  2. Пройдитесь по массиву болтов и найдите его в хэш-карте.
  3. Если он найден в хэш-карте гаек, это означает, что для этой гайки существуют болты.

Реализация:

Временная сложность этого решения составляет O(n).

Вспомогательное пространство: O(n) , потому что используется хэш-карта

Эта статья предоставлена Нитешем Кумаром . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью с помощью write.geeksforgeeks.org или отправить ее по адресу review-team@geeksforgeeks.org. Посмотрите, как ваша статья появится на главной странице GeeksforGeeks, и помогите другим гикам

РЕКОМЕНДУЕМЫЕ СТАТЬИ