Medium

题目描述

给你一个数组 favoriteCompanies，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司列表（下标从 0 开始）。

请返回不是其他任何人收藏的公司列表的子集的收藏列表的下标。你必须按升序返回下标。

示例 1：

输入：favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
输出：[0,1,4] 
解释：
下标为 2 的人收藏的公司列表 ["google","facebook"] 是下标为 0 的人收藏的公司列表 ["leetcode","google","facebook"] 的子集。
下标为 3 的人收藏的公司列表 ["google"] 既是下标为 0 的人收藏的公司列表 ["leetcode","google","facebook"] 的子集，也是下标为 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] 仍然成立。
  • 所有字符串仅包含小写英文字母。

解题思路

这道题的核心是判断一个列表是否是另一个列表的子集。我们需要找出所有不是其他列表子集的列表。

解题思路：

  1. 暴力比较法：对于每个列表，检查它是否是其他任何列表的子集。如果不是，则将其下标加入结果。

  2. 优化方法：

    • 将每个公司列表转换为集合(Set)，便于快速查找
    • 对于列表A和列表B，如果A的长度大于B的长度，那么B不可能是A的子集
    • 使用集合的子集判断方法，例如Python中的issubset()或手动实现

具体步骤：

  1. 遍历每个人的收藏列表
  2. 对于当前列表，检查是否存在其他列表包含当前列表的所有元素
  3. 如果当前列表不是任何其他列表的子集，则保留其下标
  4. 返回所有符合条件的下标

时间复杂度为O(n²×m)，其中n是列表数量，m是单个列表的平均长度。

代码实现

class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        int n = favoriteCompanies.size();
        vector<int> result;
        
        for (int i = 0; i < n; i++) {
            bool isSubset = false;
            unordered_set<string> setI(favoriteCompanies[i].begin(), favoriteCompanies[i].end());
            
            for (int j = 0; j < n; j++) {
                if (i == j || favoriteCompanies[j].size() < favoriteCompanies[i].size()) {
                    continue;
                }
                
                unordered_set<string> setJ(favoriteCompanies[j].begin(), favoriteCompanies[j].end());
                bool allFound = true;
                
                for (const string& company : favoriteCompanies[i]) {
                    if (setJ.find(company) == setJ.end()) {
                        allFound = false;
                        break;
                    }
                }
                
                if (allFound) {
                    isSubset = true;
                    break;
                }
            }
            
            if (!isSubset) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies)
        result = []
        
        for i in range(n):
            is_subset = False
            set_i = set(favoriteCompanies[i])
            
            for j in range(n):
                if i == j or len(favoriteCompanies[j]) < len(favoriteCompanies[i]):
                    continue
                
                set_j = set(favoriteCompanies[j])
                if set_i.issubset(set_j):
                    is_subset = True
                    break
            
            if not is_subset:
                result.append(i)
        
        return result

public class Solution {
    public IList<int> PeopleIndexes(IList<IList<string>> favoriteCompanies) {
        int n = favoriteCompanies.Count;
        var result = new List<int>();
        
        for (int i = 0; i < n; i++) {
            bool isSubset = false;
            var setI = new HashSet<string>(favoriteCompanies[i]);
            
            for (int j = 0; j < n; j++) {
                if (i == j || favoriteCompanies[j].Count < favoriteCompanies[i].Count) {
                    continue;
                }
                
                var setJ = new HashSet<string>(favoriteCompanies[j]);
                bool allFound = true;
                
                foreach (string company in favoriteCompanies[i]) {
                    if (!setJ.Contains(company)) {
                        allFound = false;
                        break;
                    }
                }
                
                if (allFound) {
                    isSubset = true;
                    break;
                }
            }
            
            if (!isSubset) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

var peopleIndexes = function(favoriteCompanies) {
    const result = [];
    
    for (let i = 0; i < favoriteCompanies.length; i++) {
        let isSubset = false;
        const setI = new Set(favoriteCompanies[i]);
        
        for (let j = 0; j < favoriteCompanies.length; j++) {
            if (i !== j && favoriteCompanies[j].length >= favoriteCompanies[i].length) {
                const setJ = new Set(favoriteCompanies[j]);
                if ([...setI].every(company => setJ.has(company))) {
                    isSubset = true;
                    break;
                }
            }
        }
        
        if (!isSubset) {
            result.push(i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²×m)，其中n是列表数量，m是单个列表的最大长度。需要对每个列表与其他所有列表进行比较
空间复杂度O(m)，主要用于存储集合，其中m是单个列表的最大长度