Python怎么实现两个列表的最小索引总和
这篇文章主要讲解了“Python怎么实现两个列表的最小索引总和”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Python怎么实现两个列表的最小索引总和”吧！
在萧山等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供做网站、网站制作 网站设计制作定制网站设计,公司网站建设,企业网站建设,成都品牌网站建设,全网营销推广,成都外贸网站建设公司,萧山网站建设费用合理。
题目：
假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。如果答案不止一个，则输出所有答案并且不考虑顺序。你可以假设总是存在一个答案。
示例 1:
输入: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] 输出: ["Shogun"] 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
示例 2:
输入: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun", "Burger King"] 输出: ["Shogun"] 解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
提示:
两个列表的长度范围都在 [1, 1000] 内。
两个列表中的字符串的长度将在 [1，30] 的范围内。
下标从 0 开始，到列表的长度减 1。
两个列表都没有重复的元素。
解题思路：
两个字符串数组，找重复出现的元素，返回其索引和最小的目标数组。最容易想到的解法就是用哈希映射解题，Key 存储其数组的每个元素值，Value 存储其下标索引。第一次遍历将其中一个数组添加到哈希映射，第二次遍历查找目标元素。需要维护一个最小索引和来保证查询的目标索引和为最小。
哈希表解题：
Java：
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
Map map = new HashMap<>();//建立哈希映射
for (int i = 0; i < list1.length; i++)//初次遍历将一个数组建立映射关系
map.put(list1[i], i);
List res = new ArrayList<>();//待返回的目标数组
int sum = Integer.MAX_VALUE;//sum为当前满足条件的最小索引和
for (int i = 0; i < list2.length; i++) {//第二次遍历查找目标元素
if (map.containsKey(list2[i])) {
int tmp = i + map.get(list2[i]);//当前索引和
if (tmp < sum) {//如果当前索引和更小
res.clear();//清除目标数组
res.add(list2[i]);//添加该元素
sum = tmp;// 刷新最小索引和
} else if (tmp == sum)//如果索引和相等
res.add(list2[i]);//只添加元素
}
}
return res.toArray(new String[res.size()]);//转成 string 数组
}
} Python：
class Solution: def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]: hash_map = dict()# 建立哈希映射 for i, s in enumerate(list1):# 初次遍历将一个数组建立映射关系 hash_map[s] = i min_sum = 2001# 当前满足条件的最小索引和 res = list()# 待返回的目标数组 for i, s in enumerate(list2):# 第二次枚举遍历查找目标元素 if s in hash_map: tmp = i+hash_map[s]# 当前索引和 if tmp < min_sum:# 如果当前索引和更小 res.clear()# 清除目标数组 res.append(s)# 添加该元素 min_sum = tmp# 刷新最小索引和 elif tmp == min_sum:# 如果索引和相等 res.append(s)# 只添加元素 return res
操作索引解题：
这种解法非常巧妙，虽然效率很低。以下解释摘自 LeetCode，可以作为参考扩展思路：
另一种可以遍历不同 sumsum (下标和)，并判断是否有字符串分别出现在 list1 和 list2 中且下标和为 sum。
现在我们知道下标和的值 sum 数值范围从 0 到 m + n - 1。这里 m 和 n 分别是 list1 和 list2 的长度，我们现在可以升序枚举 sum ，对于每个 sum，我们遍历 list1，假设当前下标为 i，为了得到下标和 sum，list2 中的下标 j 为 sum−i。通过这样的办法，我们不需要遍历 list2，而可以直接通过计算得到在 list2 中对应的下标。
对于每个 sum，我们遍历 list1 的所有下标，一旦有 list1 和 list2 中的字符串匹配，就把匹配字符串放入一个 res 列表中。
我们对 sum 升序数组中所有值做相同的过程，对于每个 sum 遍历完一遍 list1 之后，我们检查 res 列表是否为空。如果是空的，我们继续遍历下一个 sum 数组。如果不为空，当前的 res 就是最小下标和的数组。这是因为我们遍历 sum 的顺序是升序的，所以第一个找到的列表就是结果列表。
Java：
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
List res = new ArrayList<>();
for (int sum = 0; sum < list1.length + list2.length - 1; sum++) {
for (int i = 0; i <= sum; i++) {
if (i < list1.length && sum - i < list2.length && list1[i].equals(list2[sum - i]))
res.add(list1[i]);
}
if (res.size() > 0) break;//一旦找到最小索引和序列直接结束遍历，因为sum是递增的，之后得到的索引和一定更大
}
return res.toArray(new String[res.size()]);
}
} Python
class Solution: def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]: res = list() list1_size, list2_size = len(list1), len(list2) for min_sum in range(list1_size+list2_size-1): for i in range(min_sum+1): if i < list1_size and min_sum-i < list2_size and list1[i] == list2[min_sum-i]: res.append(list1[i]) if len(res) > 0:# 一旦找到最小索引和序列直接结束遍历，因为sum是递增的，之后得到的索引和一定更大 break return res
感谢各位的阅读，以上就是“Python怎么实现两个列表的最小索引总和”的内容了，经过本文的学习后，相信大家对Python怎么实现两个列表的最小索引总和这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！
文章名称：Python怎么实现两个列表的最小索引总和
转载源于：http://pwwzsj.com/article/gspgeo.html
