LEETCODE 1452. People Whose List of Favorite Companies Is Not a Subset of Another List 解题思路分析

题目大意:

收藏清单

给你一个数组 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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。