algorithm notes: leetcode#599 minimum index sum of two lists

Problem


Solution


Analysis

Python implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class :
def findRestaurant(self, list1, list2):
"""
:type list1: List[str]
:type list2: List[str]
:rtype: List[str]
"""
map1 = {res:ix for ix, res in enumerate(list1)}
common = dict()
minSum = len(list1) + len(list2)
for ix, res in enumerate(list2):
if res in map1:
common[res] = ix+map1[res]
minSum = min(minSum, common[res])
return [res for res, s in common.items() if s==minSum]

Java implementation

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
27
class {
public String[] findRestaurant(String[] list1, String[] list2) {
Map<String, Integer> map1 = new HashMap();
for(int i = 0; i < list1.length; i++){
map1.put(list1[i], i);
}
Map<String, Integer> common = new HashMap();
int minSum = list1.length + list2.length;
for(int i = 0; i < list2.length; i++){
String res = list2[i];
if(map1.containsKey(res)){
int curSum = i+map1.get(res);
common.put(res, curSum);
minSum = minSum > curSum ? curSum : minSum;
}
}
List<String> ans = new ArrayList<>();
for(Map.Entry<String, Integer> entry : common.entrySet()){
String res = entry.getKey();
int s = entry.getValue();
if(s==minSum){
ans.add(res);
}
}
return ans.toArray(new String[ans.size()]);
}
}

Time complexity

O(l1+l2)

Space complexity

O(l1+l2)


599. Minimum Index Sum of Two Lists
(中文版) 算法笔记: 力扣#599 两个列表的最小索引总和