# 599. Minimum Index Sum of Two Lists 两个列表的最小索引总和

@TOC

## # 题目描述

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

Note:

1. The length of both lists will be in the range of [1, 1000].
2. The length of strings in both lists will be in the range of [1, 30].
3. The index is starting from 0 to the list length minus 1.
4. No duplicates in both lists.

## # 解题方法

### # 方法一：找到公共元素再求索引和

``````class Solution(object):
def findRestaurant(self, list1, list2):
"""
:type list1: List[str]
:type list2: List[str]
:rtype: List[str]
"""
commons = [word for word in list1 if word in list2]
smallest = 1000000
for common in commons:
index1 = list1.index(common)
index2 = list2.index(common)
index = index1 + index2
if smallest > index:
smallest = index
elif smallest == index:
``````

``````class Solution(object):
def findRestaurant(self, list1, list2):
"""
:type list1: List[str]
:type list2: List[str]
:rtype: List[str]
"""
dic1 = {word:ind for ind,word in enumerate(list1)}
dic2 = {word:ind for ind,word in enumerate(list2)}
smallest = 1000000
for word in dic1:
if word in dic2:
_sum = dic1[word] + dic2[word]
if smallest > _sum:
smallest = _sum
elif smallest == _sum:
``````

### # 方法二：索引求和，使用堆弹出最小元素

``````class Solution:
def findRestaurant(self, list1, list2):
"""
:type list1: List[str]
:type list2: List[str]
:rtype: List[str]
"""
interest = dict()
for i, l in enumerate(list1):
interest[l] = [i, 100000]
for j, l in enumerate(list2):
if l in interest:
interest[l][1] = j
heap = [(sum(v), l) for l, v in interest.items()]
heapq.heapify(heap)
res = []
smallest = -1
while heap:
cursum, curl = heapq.heappop(heap)
if smallest == -1:
smallest = cursum
if smallest == cursum:
res.append(curl)
else:
break
return res
``````

## # 日期

2018 年 1 月 23 日 2018 年 11 月 16 日 —— 又到周五了！