题目描述
假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
示例 1:
输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。
示例 2:
输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
提示:
1 <= list1.length, list2.length <= 10001 <= list1[i].length, list2[i].length <= 30 list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。list1 的所有字符串都是 唯一 的。list2 中的所有字符串都是 唯一 的。
解法
方法一：哈希表
我们用一个哈希表 \(\textit{d}\) 记录 \(\textit{list2}\) 中的字符串和它们的下标，用一个变量 \(\textit{mi}\) 记录最小的下标和。
然后遍历 \(\textit{list1}\)，对于每个字符串 \(\textit{s}\)，如果 \(\textit{s}\) 在 \(\textit{list2}\) 中出现，那么我们计算 \(\textit{s}\) 在 \(\textit{list1}\) 中的下标 \(\textit{i}\) 和在 \(\textit{list2}\) 中的下标 \(\textit{j}\)，如果 \(\textit{i} + \textit{j} < \textit{mi}\)，我们就更新答案数组 \(\textit{ans}\) 为 \(\textit{s}\)，并且更新 \(\textit{mi}\) 为 \(\textit{i} + \textit{j}\)；如果 \(\textit{i} + \textit{j} = \textit{mi}\)，我们就将 \(\textit{s}\) 加入答案数组 \(\textit{ans}\)。
遍历结束后，返回答案数组 \(\textit{ans}\) 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
d = {s: i for i, s in enumerate(list2)}
ans = []
mi = inf
for i, s in enumerate(list1):
if s in d:
j = d[s]
if i + j < mi:
mi = i + j
ans = [s]
elif i + j == mi:
ans.append(s)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
Map<String, Integer> d = new HashMap<>();
for (int i = 0; i < list2.length; ++i) {
d.put(list2[i], i);
}
List<String> ans = new ArrayList<>();
int mi = 1 << 30;
for (int i = 0; i < list1.length; ++i) {
if (d.containsKey(list1[i])) {
int j = d.get(list1[i]);
if (i + j < mi) {
mi = i + j;
ans.clear();
ans.add(list1[i]);
} else if (i + j == mi) {
ans.add(list1[i]);
}
}
}
return ans.toArray(new String[0]);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> d;
for (int i = 0; i < list2.size(); ++i) {
d[list2[i]] = i;
}
vector<string> ans;
int mi = INT_MAX;
for (int i = 0; i < list1.size(); ++i) {
if (d.contains(list1[i])) {
int j = d[list1[i]];
if (i + j < mi) {
mi = i + j;
ans.clear();
ans.push_back(list1[i]);
} else if (i + j == mi) {
ans.push_back(list1[i]);
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | func findRestaurant(list1 []string, list2 []string) []string {
d := map[string]int{}
for i, s := range list2 {
d[s] = i
}
ans := []string{}
mi := 1 << 30
for i, s := range list1 {
if j, ok := d[s]; ok {
if i+j < mi {
mi = i + j
ans = []string{s}
} else if i+j == mi {
ans = append(ans, s)
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function findRestaurant(list1: string[], list2: string[]): string[] {
const d = new Map<string, number>(list2.map((s, i) => [s, i]));
let mi = Infinity;
const ans: string[] = [];
list1.forEach((s, i) => {
if (d.has(s)) {
const j = d.get(s)!;
if (i + j < mi) {
mi = i + j;
ans.length = 0;
ans.push(s);
} else if (i + j === mi) {
ans.push(s);
}
}
});
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | use std::collections::HashMap;
impl Solution {
pub fn find_restaurant(list1: Vec<String>, list2: Vec<String>) -> Vec<String> {
let mut d = HashMap::new();
for (i, s) in list2.iter().enumerate() {
d.insert(s, i);
}
let mut ans = Vec::new();
let mut mi = std::i32::MAX;
for (i, s) in list1.iter().enumerate() {
if let Some(&j) = d.get(s) {
if (i as i32 + j as i32) < mi {
mi = i as i32 + j as i32;
ans = vec![s.clone()];
} else if (i as i32 + j as i32) == mi {
ans.push(s.clone());
}
}
}
ans
}
}
|