题目描述
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).
参考答案
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
vector<string> res;
unordered_map<string, int> map;
for(size_t i = ; i< list1.size(); i++)
map[list1[i]] = i ; // list1 = key ; i = value ;
size_t min = INT_MAX;
for(size_t i = ; i<list2.size();i ++){
auto iter = map.find(list2[i]);
if(iter != map.end()){
if(iter->second + i< min ){
min = map[list2[i]] + i;
res.assign(,list2[i]); // 直接把值赋给第一个，不需要clear然后重新赋值
}else if(iter->second + i == min){
res.push_back(list2[i]);
}
}
}
return res;
}
};
分析备注
1. for 循环中，int 替换为 size_t 可以加速。
2. vector.assign(1,value) 可以实现 清除+赋值 两步操作。
3. 使用 iter -> first 和 iter -> second 可以更快。