Легкий
Проблема
Предположим, Энди и Дорис хотят выбрать ресторан для ужина, и у них обоих есть список любимых ресторанов, представленный строками.
Вам нужно помочь им найти общий интерес с помощью наименьшей суммы индекса списка. Если между ответами есть выбор, выведите все ответы без требования порядка. Можно предположить, что всегда существует ответ.
Пример 1:
Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] Output: ["Shogun"] Explanation: The only restaurant they both like is "Shogun".
Пример 2:
Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun", "Burger King"] Output: ["Shogun"] Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).
Примечание.
- Длина обоих списков будет в диапазоне [1, 1000].
- Длина строк в обоих списках будет в диапазоне [1, 30].
- Индекс начинается с 0 до длины списка минус 1.
- Нет дубликатов в обоих списках.
Решение
Используйте хэш-карту для хранения индексов ресторанов в list1 и повторите list2, чтобы получить тот, у которого сумма индексов наименьшая.
Сложность
Предположим, что m и n обозначают количество ресторанов list1 и list2. Для построения хеш-карты требуется время O(m). И тогда в среднем/худшем случае требуется время O(n)/O(nlogm) для итерации list2 и проверки наличия элементов в list1. Следовательно, его временная сложность составляет O(m + n)/O(m + nlogm) в среднем/наихудшем случае.
Требуется O(m) дополнительного пространства для поддержки хеш-карты.
