### 题目描述 假设 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 中的所有字符串都是 唯一 的。 ### 题目解答 最原始的思路就是，比如从和为0，和为1...和为n这样遍历，一直寻找到共同爱好为止，这样的复杂度为O(n^2)。 #### 思路 因此需要考虑将我们进行记录，以空间换时间。 采用hash表记录list1中<餐厅-索引>的键值对，这样再list2中遍历匹配的时候，每次访问都是O(1)。这样只需要遍历两个数组各1次即可。 **算法复杂度：** 设2个数组长度为m和n 时间复杂度：都遍历一次O(m+n) 空间复杂度：可以先比较长度，选择记录较短的数组，这样复杂度为O(min(m, n)) #### 代码实现 ```python class Solution: def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]: dic = dict() for i in range(len(list1)): dic[list1[i]] = i min_index = len(list1) + len(list2) - 2 res = list() for j in range(len(list2)): if j > min_index: break if list2[j] in dic.keys(): if dic[list2[j]] + j < min_index: min_index = dic[list2[j]] + j res = [list2[j]] elif dic[list2[j]] + j == min_index: res.append(list2[j]) return res ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复