LeetCode 题解工作台
收藏清单
给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（ 下标从 0 开始 ）。 请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标 。 下标需要按升序排列 。 示例 1： 输入： favoriteComp…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以将每个公司映射到一个唯一的整数，然后对于每个人，我们将他们收藏的公司转换为整数集合，最后判断是否存在一个人的收藏公司是另一个人的子集。 时间复杂度 $(n \times m \times k + n^2 \times m)$，空间复杂度 $O(n \times m)$。其中 和 分别是 `favoriteCompanies` 的长度和每个公司清单的平均长度，而 是每个公司的平均长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。
请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。
示例 1：
输入：favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]] 输出：[0,1,4] 解释： favoriteCompanies[2]=["google","facebook"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。 favoriteCompanies[3]=["google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 和 favoriteCompanies[1]=["google","microsoft"] 的子集。 其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 [0,1,4] 。
示例 2：
输入：favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]] 输出：[0,1] 解释：favoriteCompanies[2]=["facebook","google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集，因此，答案为 [0,1] 。
示例 3：
输入：favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]] 输出：[0,1,2,3]
提示：
1 <= favoriteCompanies.length <= 1001 <= favoriteCompanies[i].length <= 5001 <= favoriteCompanies[i][j].length <= 20favoriteCompanies[i]中的所有字符串 各不相同 。- 用户收藏的公司清单也 各不相同 ，也就是说，即便我们按字母顺序排序每个清单，
favoriteCompanies[i] != favoriteCompanies[j]仍然成立。 - 所有字符串仅包含小写英文字母。
解题思路
方法一：哈希表
我们可以将每个公司映射到一个唯一的整数，然后对于每个人，我们将他们收藏的公司转换为整数集合，最后判断是否存在一个人的收藏公司是另一个人的子集。
时间复杂度 ，空间复杂度 。其中 和 分别是 favoriteCompanies 的长度和每个公司清单的平均长度，而 是每个公司的平均长度。
class Solution:
def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
idx = 0
d = {}
n = len(favoriteCompanies)
nums = [set() for _ in range(n)]
for i, ss in enumerate(favoriteCompanies):
for s in ss:
if s not in d:
d[s] = idx
idx += 1
nums[i].add(d[s])
ans = []
for i in range(n):
if not any(i != j and (nums[i] & nums[j]) == nums[i] for j in range(n)):
ans.append(i)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2 * m) in the worst case, where n is the number of people and m is the average number of companies per list, due to pairwise subset checks. Space complexity is O(n * m) for storing hash sets of each list. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
You might get hints about using hashing for subset checks to avoid TLE.
- question_mark
Expect questions on handling large lists and optimizing comparisons.
- question_mark
Clarify whether duplicate company names exist and confirm subset definitions.
常见陷阱
外企场景- error
Forgetting to handle lists with identical companies correctly and treating them as subsets.
- error
Not converting lists to sets, which leads to O(n * m^2) time complexity.
- error
Returning indices unsorted, which violates problem requirements.
进阶变体
外企场景- arrow_right_alt
Return lists that are subsets of at least one other list instead of non-subsets.
- arrow_right_alt
Find non-subset lists but return them as company names instead of indices.
- arrow_right_alt
Optimize for memory by using bitmask encoding for smaller alphabets of company names.