Сложный уровень
Легкий
спросил в
Амазонка, поход, Adobe, Makemytrip
Четыре решения Обсуждено
- Грубая сила
- Хеш-таблица
Разбираемся в проблеме:
Дан набор из n гаек разных размеров и n болтов разных размеров. Между гайками и болтами существует взаимное соответствие. Эффективно подбирайте гайки и болты.
каждый элемент гайки и болта может быть любым из этих элементов! # $ % & * @ ^ ~
орехи [] = {'@', '#', '$', '%', '^', '&'}
болты [] = {‘$’, ‘%’, ‘&’, ‘^’, ‘@’, ‘#’}
печатать по порядку! # $ % & * @ ^ ~ если элемент гайки совпадает с элементом болта
1. Грубая сила
Шаги решения
мы можем использовать два вложенных цикла, и для каждой гайки мы будем перебирать все болты или наоборот.
Анализ решения
поскольку мы используем два вложенных цикла, тогда временная сложность будет равна размеру гайки * размеру болта, который O (размер гайки * размер болта)
и нам не нужно использовать дополнительное пространство, поэтому сложность пространства будет постоянной
2. Хэш-таблица
Шаги решения
1. мы используем две хеш-таблицы для хранения символов гаек и болтов.
2. Затем мы повторяем гайку или болт в соответствии с вашими соображениями, и если массив гаек повторяется, то проверьте этот символ. Если он находится в хеш-таблице болтов, и если он присутствует, то вы получили пару гайки и болта для этого символа
3. Сделайте это для всех левых символов в заданном массиве орехов.
Код решения С++
Анализ решения
Временная сложность будет O (n), так как вставка, поиск и извлечение занимают постоянное время. Поскольку в одной итерации номер операции хеширования (поиск) равен 2. Всего операция будет 2 * n, поэтому временная сложность будет O (n):
Пространственная сложность будет O(n)
