整体思路
- 解题核心是处理一个集合是否为另一个集合的子集，且该判断过程对时间复杂度影响很大。
- 细节注意
- 提示要求返回清单，其下标需要按升序排列
- 锁定目标集合，遍历其他集合是否包含 目标集合
直接使用List类的containsAll方法
代码
/**
* 使用 containsAll 优化代码
* 超时
*/
public List<Integer> peopleIndexes2(List<List<String>> favoriteCompanies) {
List<Integer> ans = new ArrayList<>();
int size = favoriteCompanies.size();
boolean[] record = new boolean[size];
for (int i = 0; i < size ; i++) {
List<String> one = favoriteCompanies.get(i);
boolean flag =true;
for (int j = 0; j < size; j++) {
List<String> two = favoriteCompanies.get(j);
if(i!=j&&two.size()>=one.size()){
if(two.containsAll(one)){
flag=false;
break;
}
}
}
if(flag) ans.add(i);
}
return ans;
}
HashSet重构List集合
- 由于上面超时，关键是由调用containsAll方法且其复杂度高所致的，所以通过重构输入集合，改为Set集合来优化判断子集操作。
代码
/**
* 216 ms
*
* List转Set优化 150ms
*
*/
public List<Integer> peopleIndexes3(List<List<String>> favoriteCompanies) {
List<Integer> ans=new ArrayList<>();
List<Set<String>> list=new ArrayList<>();
// for(List<String> fa:favoriteCompanies){
// Set<String> set=new HashSet<>(fa);
// list.add(set);
// }
for(List<String> fa:favoriteCompanies){
Set<String> set=new HashSet<>();
for(String str:fa){
set.add(str);
}
list.add(set);
}
for(int i=0;i<favoriteCompanies.size();i++){
Set<String> one=list.get(i);
boolean flag=true;
for(int j=0;j<favoriteCompanies.size();j++){
Set<String> two = list.get(j);
if(two.size()>=one.size()&&i!=j){
if(two.containsAll(one)){
flag=false;
break;
}
}
}
if(flag) ans.add(i);
}
return ans;
}
- 在List转Set集合过程中，调用自带构造方法
Set<String> set=new HashSet<>(list);效率不如 逐条转换
小结
-
HashSet的containsAll方法效率比ArrayList的contains方法高
-
目前最佳耗时150ms左右 ，应该还有更优解吧
参考链接：