原题

1452.收藏清单

题解

方法一 暴力法

对于每个清单，暴力遍历遍历所有其他清单，检查是否是其他的清单子集，是的话加入序号，不是就去掉。 本思路iava代码示例：

/* @v7fgg 执行用时：297 ms, 在所有 Java 提交中击败了38.53%的用户 内存消耗：48.6 MB, 在所有 Java 提交中击败了100.00%的用户 2020年6月30日 15:09 */ class Solution { public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) { List<Integer> ans=new ArrayList<>();//用于存储答案的list Map<Integer,Set<String>> m=new HashMap<>(); //用于存储favoriteCompanies里list序号i（key），以及i号list所有的元素的集合（value） for(int i=0;i<favoriteCompanies.size();i++){ Set<String> s=new HashSet<>(); for(String str:favoriteCompanies.get(i)){ s.add(str); } m.put(i,s); } //j定位的是需要进行比较的list，就是判断j号list是其他的子集 for(int j=0;j<favoriteCompanies.size();j++){ ans.add(j); boolean find=true; //需要把j里面的每一个元素，检查在不在k里（j是不是k的子集） for(int k=0;k<favoriteCompanies.size();k++){ if(k!=j){//避免和自己比 find=true;//先暂定是可以找到的，假如发现不匹配就转为false for(String string:favoriteCompanies.get(j)){ if(!m.get(k).contains(string)){ find=false; break; //不匹配时立刻false并且不再在此k里面进行比对 } } } else{continue;} if(find){break;} //找到后，就已经没有必要继续为j找了 } if(find){ ans.remove(ans.size()-1); } } return ans; } }

方法二

此方法利用了containsAll方法来判断某集合或者list是否为另一个的子集，不过要注意在比对set和list时的复杂度区别。 本思路java代码示例：

/* @v7fgg 执行用时：1208 ms, 在所有 Java 提交中击败了5.07%的用户 内存消耗：48.2 MB, 在所有 Java 提交中击败了100.00%的用户 2020年6月30日 19:59 */ class Solution { public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) { List<Integer> ans=new ArrayList<>(); for(int i=0;i<favoriteCompanies.size();i++){ ans.add(i); for(int j=0;j<favoriteCompanies.size();j++){ if(i!=j){ //下边直接用ArrayList用containsAll会超时，前者O(n)后者O(1) if(new HashSet<>(favoriteCompanies.get(j)).containsAll(new HashSet<>(favoriteCompanies.get(i)))){ ans.remove(ans.size()-1); break; } } } } return ans; } }

方法二参考资料1