LeetCode 599. Minimum Index Sum of Two Lists(两个列表的最小索引和)
题目描述
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:
- The length of both lists will be in the range of [1, 1000].
- The length of strings in both lists will be in the range of [1, 30].
- The index is starting from 0 to the list length minus 1.
- No duplicates in both lists.
解法一
思路
想要得到“最小索引和”那就免不了要遍历两个数组了。注意到只有值相等的元素才能够用来计算索引和,所以我们只需要遍历其中一个数组,而把另一个数组当作Map(key为元素值,value为索引)来查表就可以了。这样在遍历其中一个数组时,对于每个元素,只用在Map中找到相同元素,得到其在另一数组中的索引,与自身的索引相加即为索引和;遍历完成得到的最小索引和即为最终结果。
这里还有一个剪枝的步骤,遍历每个元素时,我们会维护一个当前得到的最小索引和,而如果仅当前元素的索引就已经比当前最小索引和大的话,也就没有继续遍历下去的意义了(当前元素索引与Map得到的另一数组中的索引的和一定大于最小索引和)。
Python
class Solution:
def findRestaurant(self, list1, list2):
"""
:type list1: List[str]
:type list2: List[str]
:rtype: List[str]
"""
min_index_sum = sys.maxsize
result = []
list1_dict = {k: v for v, k in enumerate(list1)}
for index, item in enumerate(list2):
if index > min_index_sum:
break
if item in list1_dict:
current_index_sum = index + list1_dict[item]
if current_index_sum < min_index_sum:
min_index_sum = current_index_sum
result = []
if current_index_sum == min_index_sum:
result.append(item)
return result
Java
public class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
int minIndexSum = Integer.MAX_VALUE;
List<String> resultList = new ArrayList<>();
Map<String, Integer> list1Map = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
list1Map.put(list1[i], i);
}
for (int i = 0; i < list2.length; i++) {
if (i > minIndexSum) {
break;
}
String item = list2[i];
if (list1Map.containsKey(item)) {
int currentIndexSum = i + list1Map.get(item);
if (currentIndexSum < minIndexSum) {
minIndexSum = currentIndexSum;
resultList.clear();
}
if (currentIndexSum == minIndexSum) {
resultList.add(item);
}
}
}
String[] result = new String[resultList.size()];
return resultList.toArray(result);
}
}
C++
class Solution {
public:
vector<string> findRestaurant(vector<string> &list1, vector<string> &list2) {
int minIndexSum = INT_MAX;
vector<string> result;
unordered_map<string, int> list1Map;
for (int i = 0; i < list1.size(); i++) {
list1Map.insert(pair<string, int>(list1[i], i));
}
for (int i = 0; i < list2.size(); i++) {
if (i > minIndexSum) {
break;
}
string item = list2[i];
if (list1Map.find(item) != list1Map.end()) {
int currentIndexSum = i + list1Map[item];
if (currentIndexSum < minIndexSum) {
minIndexSum = currentIndexSum;
result.clear();
}
if (currentIndexSum == minIndexSum) {
result.push_back(item);
}
}
}
return result;
}
};