class Solution {
public:
vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
}
};
1452. 收藏清单
给你一个数组 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 <= 1001 <= favoriteCompanies[i].length <= 5001 <= favoriteCompanies[i][j].length <= 20favoriteCompanies[i] 中的所有字符串 各不相同 。favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。原站题解
python3 解法, 执行用时: 1444 ms, 内存消耗: 30.1 MB, 提交时间: 2023-03-09 17:40:06
class Solution:
def peopleIndexes(self, nums: List[List[str]]) -> List[int]:
return [j for j in range(len(nums)) if(len([i for i in range(len(nums)) if i!=j and len(set(nums[i])&set(nums[j]))==len(nums[j])])==0)]
python3 解法, 执行用时: 140 ms, 内存消耗: 30.3 MB, 提交时间: 2023-03-09 17:38:58
class Solution:
def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
n = len(favoriteCompanies)
companyMap = {}
fcs = [set() for _ in range(n)]
for i, f in enumerate(favoriteCompanies):
for name in f:
if name not in companyMap:
companyMap[name] = len(companyMap)
fcs[i].add(companyMap[name])
subset = set()
for i in range(n):
if i in subset:
continue
for j in range(i + 1, n):
if j in subset:
continue
if fcs[i].issubset(fcs[j]):
subset.add(i)
break
if fcs[j].issubset(fcs[i]):
subset.add(j)
return list(filter(lambda x: x not in subset, range(n)))
java 解法, 执行用时: 377 ms, 内存消耗: 49.5 MB, 提交时间: 2023-03-09 17:37:19
class Solution {
public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
int n = favoriteCompanies.size();
Set<Integer>[] arr = new Set[n];
for (int i = 0; i < n; i++) {
arr[i] = new HashSet(favoriteCompanies.get(i));
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
boolean flag = true;
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
if (arr[j].containsAll(arr[i])) {
flag = false;
break;
}
}
if (flag) ans.add(i);
}
return ans;
}
}