收藏清单--排序

LeetCode

收藏清单

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

解法：直接遍历

解题思路：

利用Java的set来判断一个清单是否是另一个清单的子集

代码如下：

class Solution
{
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        List<Integer> result = new ArrayList<>();
        int n = favoriteCompanies.size();
        for (int i = 0; i < n; i++) 
        {
            boolean flag = true;
            for (int j = 0; j < n; j++) 
            {
                if (i == j) 
                {
                    continue;
                }
                List<String> companies1 = favoriteCompanies.get(i);
                List<String> companies2 = favoriteCompanies.get(j);
                Set<String> set = new HashSet<>(companies2);
                if (set.containsAll(companies1)) 
                {
                    flag = false;
                    break;
                }
            }
            if (flag) 
            {
                result.add(i);
            }
        }
        return result;
    }
}

优化后的

class Solution {
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        int n = favoriteCompanies.size();
        Set<String>[] 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;
    }
}

感想

说实话，这道题让我有点懵，两个for循环一开始就想到了，但是我觉得效率可能太低了吧，所以一直在想其他方法，没想到最后是直接用最粗暴的方法