599. 2つのリストの最小インデックス合計python（python + cpp）
599 Minimum Index Sum Two Listspython Python Cpp
トピック：
AndyとDorisが夕食にレストランを選びたいと思っていて、どちらも文字列で表されたお気に入りのレストランのリストを持っているとします。
あなたは彼らが最小のリストインデックスの合計で彼らの共通の興味を見つけるのを助ける必要があります。回答の間に選択の同点がある場合は、順序を必要とせずにすべてを出力します。あなたは常に答えが存在すると仮定することができます。
例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'.例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).注意：
両方のリストの長さは[1、1000]の範囲になります。
両方のリストの文字列の長さは[1、30]の範囲になります。
インデックスは0から始まり、リストの長さから1を引いたものです。両方のリストに重複はありません。
説明：
非常に遅いPythonコード：
class Solution(object): def findRestaurant(self, list1, list2): ''' :type list1: List[str] :type list2: List[str] :rtype: List[str] ''' both=[x for x in list1 if x in list2] min_index=len(list1)+len(list2) result=[] for b in both: sum_index=list1.index(b)+list2.index(b) min_index=min(min_index,sum_index) if min_index==sum_index: result.append(b) return result 1つを使用する必要がありますdict()、速度と高速になります、コード：
class Solution: def findRestaurant(self, list1, list2): ''' :type list1: List[str] :type list2: List[str] :rtype: List[str] ''' _dict={} for i,v in enumerate(list1): _dict[v]=i min_indexSum=float('inf') result=[] for i,v in enumerate(list2): if v in _dict: if i+_dict[v]<min_indexSum: min_indexSum=i+_dict[v] result=[v] elif i+_dict[v]==min_indexSum: result.append(v) return result c ++コード：
class Solution { public: vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) { map<string,int>_map for (int i=0i<list1.size()i++) { _map[list1[i]]=i } int minIndexSum=INT_MAX vector<string> result for (int i=0i<list2.size()i++) { string word=list2[i] if (_map.count(word)) { if(i+_map[word]<minIndexSum) { minIndexSum=i+_map[word] result={word} } else if(i+_map[word]==minIndexSum) result.push_back(word) } } return result } } 総括する：
インデックス付きトピックの場合、値を取得するためにインデックスが頻繁に必要になる場合は、毎回使用する前にdictを使用して保存することがあります。index()トラバースははるかに高速です。