leetcode 599. Minimum Index Sum of Two Lists

浅浅的花香味﹌ 2022-06-15 09:00 124阅读 0赞

# 1.题目 #

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.  
有两个包含餐馆名的数组，求他们共有的最小下标和的餐馆名称。  
Example 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”.

Example 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).

# 2.分析 #

两个数组都需要遍历一遍。  
遍历第一个数组，用哈希表或字典或map记录元素值对应下标。  
遍历第二个数组，相同元素的下标值相加，找出最小的。

# 3.代码 #

class Solution(object):
        def findRestaurant(self, list1, list2):
            pos1={v:pos for pos,v in enumerate(list1)}
            length=len(list2)+len(list1)
            result=[]
            mind=length
            for i,v in enumerate(list2):
                j=pos1.get(v,length)
                if i+j < mind:#更新最小值
                    result=[v]
                    mind=i+j
                elif i+j==mind:#最小值一样
                    result.append(v)
            return result