関小君刷题记

题目大意：

收藏清单

给你一个数组 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] 仍然成立。
• 所有字符串仅包含小写英文字母。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1452

解题思路分析：

java语言中我们可以使用containsAll方法来判断一个集合是否是另一个集合的子集，由于本题的数据规模并不大，因此可以采用暴力枚举法来判断包含关系。解题时需要注意一点，由于List类型在做contains处理时的时间复杂度为n（n是List内元素个数），因此将List转化成时间复杂度为1的Set后再去解题，效率会大大提高。

实现代码：

public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
    List<Set<String>> list = new ArrayList<>();
    for(List<String> l : favoriteCompanies){ // 将list转为set
        list.add(new HashSet<>(l));
    }
    List<Integer> res = new ArrayList<>(); // 返回结果
    for(int i=0;i<list.size();i++){ // 循环每一个set
        Set<String> current = list.get(i); // 当前set
        boolean isValid=true; // 当前set是否不存在父集
        for(int j=0;j<list.size();j++){ // 循环其他每一个set
            if(i==j) continue;
            if(list.get(j).size()<current.size()) continue;
            if(list.get(j).containsAll(current)){
                isValid=false;
                break;
            }
        }
        if(isValid) res.add(i);
    }
    return res;
}

本题解法执行时间为196ms。

Runtime: 196 ms, faster than 50.00% of Java online submissions for People Whose List of Favorite Companies Is Not a Subset of Another List.

Memory Usage: 59.2 MB, less than 100.00% of Java online submissions for People Whose List of Favorite Companies Is Not a Subset of Another List.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1452-people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list-解题思路分析/