599. 两个列表的最小索引总和

🟢 🔖 数组 哈希表 字符串 🔗 力扣open in new window LeetCodeopen in new window

题目

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all thecommon strings with the least index sum. Return the answer in any order.

Example 1:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.

Example 3:

Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output: ["sad","happy"]
Explanation: There are three common strings:
"happy" with index sum = (0 + 1) = 1.
"sad" with index sum = (1 + 0) = 1.
"good" with index sum = (2 + 2) = 4.
The strings with the least index sum are "sad" and "happy".

Constraints:

1 <= list1.length, list2.length <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i] and list2[i] consist of spaces ' ' and English letters.
All the strings of list1 are unique.
All the strings of list2 are unique.
There is at least a common string between list1 and list2.

题目大意

假设 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 <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
list1 的所有字符串都是唯一的。
list2 中的所有字符串都是唯一的。

解题思路

建立映射：
- 先遍历 list1，记录每个餐厅的名称和对应的索引，以键值对形式存入哈希表 map1。
查找交集：
- 遍历 list2，对于每个餐厅名，检查它是否存在于 map1。
- 如果存在，则计算索引和 sum = i + map1[restaurant]。
更新结果：
- 维护一个变量 minSum，记录当前最小的索引和。
- 如果当前餐厅的索引和小于 minSum，则更新 minSum，同时清空结果列表 result 并加入当前餐厅。
- 如果当前餐厅的索引和等于 minSum，则将餐厅加入结果列表。
返回结果：
- 遍历结束后，返回结果列表 result。

复杂度分析

时间复杂度：O(m + n)，
- 构建哈希表需要遍历 list1，时间复杂度为 O(m)。
- 查找交集需要遍历 list2，时间复杂度为 O(n)。
- 总时间复杂度为 O(m + n)。
空间复杂度：O(m)，哈希表存储 list1，需要 O(m) 的额外空间。

代码

/**
 * @param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}
 */
var findRestaurant = function (list1, list2) {
	// 将 list1 中的餐厅及索引存入哈希表
	const map1 = new Map();
	for (let i = 0; i < list1.length; i++) {
		map1.set(list1[i], i);
	}

	let minSum = Infinity; // 记录最小的索引和
	const result = []; // 存储结果

	// 遍历 list2，计算交集和索引和
	for (let j = 0; j < list2.length; j++) {
		const restaurant = list2[j];
		if (map1.has(restaurant)) {
			const sum = j + map1.get(restaurant); // 索引和
			if (sum < minSum) {
				minSum = sum; // 更新最小索引和
				result.length = 0; // 清空结果
				result.push(restaurant);
			} else if (sum === minSum) {
				result.push(restaurant); // 添加到结果中
			}
		}
	}

	return result;
};

599. 两个列表的最小索引总和

# 599. 两个列表的最小索引总和

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

599. 两个列表的最小索引总和

题目

题目大意

解题思路

复杂度分析

代码

相关题目