Легкий
Проблема
Предположим, Энди и Дорис хотят выбрать ресторан для ужина, и у них обоих есть список любимых ресторанов, представленный строками.
Вам нужно помочь им найти общий интерес с помощью наименьшей суммы индекса списка. Если между ответами есть выбор, выведите все ответы без требования порядка. Можно предположить, что всегда существует ответ.
Пример 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, чтобы получить тот, у которого сумма индексов наименьшая.
| # Python3 | |
| class Solution: | |
| def findRestaurant(self, list1, list2): | |
| """ | |
| :type list1: List[str] | |
| :type list2: List[str] | |
| :rtype: List[str] | |
| """ | |
| # approach: use a hash map to save index of list1 | |
| restaurant_map = {restaurant: i for i, restaurant in enumerate(list1)} | |
| least_index_sum = len(list1) + len(list2) | |
| result = [] | |
| for i, restaurant in enumerate(list2): | |
| index_sum = i + restaurant_map.get(restaurant, least_index_sum) | |
| if index_sum < least_index_sum: | |
| least_index_sum = index_sum | |
| result = [restaurant] | |
| elif index_sum == least_index_sum: | |
| result.append(restaurant) | |
| return result |
Сложность
Предположим, что m и n обозначают количество ресторанов list1 и list2. Для построения хеш-карты требуется время O(m). И тогда в среднем/худшем случае требуется время O(n)/O(nlogm) для итерации list2 и проверки наличия элементов в list1. Следовательно, его временная сложность составляет O(m + n)/O(m + nlogm) в среднем/наихудшем случае.
Требуется O(m) дополнительного пространства для поддержки хеш-карты.
