两个列表的最小索引总和

难度: Easy

假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。如果答案不止一个，则输出所有答案并且不考虑顺序。你可以假设答案总是存在。

示例 1:

输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:

输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

提示:

1 <= list1.length, list2.length <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
list1 的所有字符串都是唯一的。
list2 中的所有字符串都是唯一的。

Submission

运行时间: 32 ms

内存: 16.4 MB

from typing import List

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        # 创建一个字典来存储list1中餐厅及其索引
        restaurant_dict = {restaurant: index for index, restaurant in enumerate(list1)}
        
        min_index_sum = float('inf')  # 初始化最小索引和为无穷大
        common_restaurants = []  # 存储共同喜爱的餐厅
        
        # 遍历list2，查找共同喜爱的餐厅并计算索引和
        for index, restaurant in enumerate(list2):
            if restaurant in restaurant_dict:
                index_sum = index + restaurant_dict[restaurant]
                if index_sum < min_index_sum:
                    # 找到了更小的索引和，更新结果
                    min_index_sum = index_sum
                    common_restaurants = [restaurant]
                elif index_sum == min_index_sum:
                    # 索引和相同，添加到结果列表中
                    common_restaurants.append(restaurant)
        
        return common_restaurants

solution = Solution()
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
print(solution.findRestaurant(list1, list2))  # 输出: ["Shogun"]

list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["KFC", "Shogun", "Burger King"]
print(solution.findRestaurant(list1, list2))  # 输出可能为["Shogun"]或["Burger King"]或["KFC"]中的一个，因为题目要求不考虑顺序，并且示例中存在错误。
# 但实际上，根据题目要求，我们应该输出["Shogun"]，因为它具有最小的索引和1(0+1)。上面的代码会正确输出["Shogun"]。

Explain

该题解的思路是先用一个字典来存储list1中每个餐厅的索引，以便在遍历list2时能快速查找共同喜爱的餐厅及其在list1中的索引。然后遍历list2，对于每个餐厅，如果它在list1中出现过，就计算它在两个列表中的索引和。如果该索引和小于当前的最小索引和，就更新最小索引和，并将该餐厅作为当前的结果；如果该索引和等于当前的最小索引和，就将该餐厅添加到结果列表中。最终返回所有具有最小索引和的共同喜爱餐厅。

时间复杂度: O(m+n)

空间复杂度: O(m+n)

from typing import List

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        # 创建一个字典来存储list1中餐厅及其索引
        restaurant_dict = {restaurant: index for index, restaurant in enumerate(list1)}
        
        min_index_sum = float('inf')  # 初始化最小索引和为无穷大
        common_restaurants = []  # 存储共同喜爱的餐厅
        
        # 遍历list2，查找共同喜爱的餐厅并计算索引和
        for index, restaurant in enumerate(list2):
            if restaurant in restaurant_dict:
                index_sum = index + restaurant_dict[restaurant]
                if index_sum < min_index_sum:
                    # 找到了更小的索引和，更新结果
                    min_index_sum = index_sum
                    common_restaurants = [restaurant]
                elif index_sum == min_index_sum:
                    # 索引和相同，添加到结果列表中
                    common_restaurants.append(restaurant)
        
        return common_restaurants

Explore

在将list1的餐厅名称存入字典时，如果存在重复的餐厅名称，字典将只保留该名称最后出现的索引。这是因为在构建字典时，如果字典中已经存在某个键（餐厅名称），对同一键的后续赋值会覆盖前面的值。因此，只有list1中每个餐厅名称最后一次出现的索引会被记录在字典中。

初始化`min_index_sum`为无穷大是为了确保任何实际计算得到的索引和都会小于这个初始值。这样，第一次遇到共同的餐厅时，就可以将实际的索引和设置为新的最小值。如果初始化为具体数值，可能会遇到没有任何索引和比它小的情况，导致结果错误。使用无穷大作为初始化值是一种常用的技术，以保证比较逻辑的正确性。

当找到一个新的最小索引和时，意味着之前在`common_restaurants`列表中存储的餐厅不再是最小索引和的餐厅。因此，先将`common_restaurants`列表清空，然后将当前餐厅添加到这个新的空列表中。这样，`common_restaurants`始终只包含具有当前最小索引和的餐厅。

如果list2中的某个餐厅不在list1中，那么这个餐厅名称在字典`restaurant_dict`中找不到匹配项。因此，当执行检查`if restaurant in restaurant_dict`时，这个条件将为假，算法不会执行任何与该餐厅相关的索引和计算或更新操作。这意味着只有在两个列表中都出现的餐厅才会被考虑进最小索引和的计算中。