收藏清单

难度: Medium

给你一个数组 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 <= 100
1 <= favoriteCompanies[i].length <= 500
1 <= favoriteCompanies[i][j].length <= 20
favoriteCompanies[i] 中的所有字符串 各不相同 。
用户收藏的公司清单也 各不相同 ，也就是说，即便我们按字母顺序排序每个清单， favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
所有字符串仅包含小写英文字母。

Submission

运行时间: 60 ms

内存: 30.9 MB

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies)
        compSets = [set(favList) for favList in favoriteCompanies] # list转化为set，节省后续时间
        tops = set(range(n)) # 如果一个下标在tops内，说明他此时没被判定为其他用户的子集

        for i in range(n):
            if i not in tops: continue # 当前用户的清单已是之前的清单的子集了，不用继续考虑他
            for j in range(i+1, n): # 与i之前用户的子集关系已经在之前用户的外层循环检查过了，只需往i后检查
                if j not in tops: continue
                if i in tops and compSets[i] < compSets[j]: # 当前用户为子集（先判断当前用户没被移除，再判断子集）
                    tops.remove(i)
                elif compSets[i] > compSets[j]: # 后续被检查的用户j是否为子集
                    tops.remove(j)
        return list(tops)

Explain

该题解采用集合操作来确定是否有一个收藏清单是另一个收藏清单的子集。首先，每个用户的收藏清单都转换为集合，以方便后续操作。使用一个集合tops来存储所有的索引，代表每个用户的收藏清单初始状态下认为都不是其他清单的子集。然后通过双重循环遍历所有的清单组合，比较两个集合的子集关系。如果发现一个集合是另一个集合的子集，那么将子集对应的索引从tops中移除。最终，tops中剩余的索引即为不是任何其他收藏清单子集的收藏清单索引。

时间复杂度: O(n^2 * min(m, n))

空间复杂度: O(n + nm)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies) # 收藏清单的数量
        compSets = [set(favList) for favList in favoriteCompanies] # 将每个收藏清单转换为集合
        tops = set(range(n)) # 初始化tops集合，包含所有索引

        for i in range(n):
            if i not in tops: continue # 如果i已经是某个其他清单的子集，则跳过
            for j in range(i+1, n): # 只比较后面的清单，避免重复比较
                if j not in tops: continue # 如果j已经是某个其他清单的子集，则跳过
                if compSets[i] < compSets[j]: # 检查是否i是j的子集
                    tops.remove(i)
                    break # 一旦确认为子集，无需继续比较
                elif compSets[j] < compSets[i]: # 检查是否j是i的子集
                    tops.remove(j)
        return list(tops) # 返回结果列表

Explore

在算法中使用集合来存储每个用户的收藏清单是因为集合（Set）提供了高效的成员检查和去重功能。此外，集合数据结构支持高效的集合运算，如检查子集关系，这是解决问题的关键操作。使用集合能够简化代码并提高性能，特别是在涉及大量数据和需要频繁检查成员资格或进行集合比较的场景中。

该逻辑基于一个前提，即如果一个清单已经确定为另一个清单的子集，则在后续比较中，无需再将其作为主体进行子集检查，因为它不可能是最终结果的一部分。这种处理方式不会导致漏掉必要的比较，因为一旦一个清单被识别为子集，它就已经不满足题目要求的独立性。这种方法能有效减少不必要的比较，提高算法效率。

使用 '<' 运算符来检查一个集合是否为另一个集合的真子集是准确的。然而，这种方法的效率问题在于，每次子集检查都可能需要遍历整个集合来确认所有元素是否都属于另一集合，导致操作的时间复杂度为 O(n)。在最坏的情况下，需要对所有清单对进行这样的检查，导致总体时间复杂度可能高达 O(n^2 * m)，其中 m 是清单中平均元素数量。

根据代码实现，最终返回的结果列表是从一个集合（set）中转换而来的。集合在Python中是无序的，因此直接从集合转换得到的列表顺序是不确定的。如果题目要求结果必须是升序的，那么在返回结果之前需要对列表进行额外的排序操作，使用例如 list.sort() 或 sorted() 方法来保证列表是按照升序排列。