使用常见食材的团体菜肴

Question

我正在研究以下问题：假设您有一个菜肴列表，其中每道菜都与配料列表相关联。将具有常见成分的菜肴分组在一起。例如：输入："Pasta" -> ["Tomato Sauce", "Onions", "Garlic"] "Chicken Curry" --> ["Chicken", "Curry Sauce"] "Fried Rice" --> ["Rice", "Onions", "Nuts"] "Salad" --> ["Spinach", "Nuts"] "Sandwich" --> ["Cheese", "Bread"] "Quesadilla" --> ["Chicken", "Cheese"] 输出：("Pasta", "Fried Rice") ("Fried Rice, "Salad")("Chicken Curry", "Quesadilla")("Sandwich", "Quesadilla") 另外，时间和空间的复杂性是什么？我想出了下面的代码。有没有更好的方法来解决这个问题？看起来算法是图论中的连接组件。public static void main(String[] args) {    List<String> ing1 = Arrays.asList("Tomato Sauce", "Onions", "Garlic");    List<String> ing2 = Arrays.asList("Chicken", "Curry Sauce");    List<String> ing3 = Arrays.asList("Rice", "Onions", "Nuts");    List<String> ing4 = Arrays.asList("Spinach", "Nuts");    List<String> ing5 = Arrays.asList("Cheese", "Bread");    List<String> ing6 = Arrays.asList("Chicken", "Cheese");    Map<String, List<String>> map = new HashMap<>();    map.put("Pasta", ing1);    map.put("Chicken Curry", ing2);    map.put("Fried Rice", ing3);    map.put("Salad", ing4);    map.put("Sandwich", ing5);    map.put("Quesadilla", ing6);    System.out.println(group(map));}private static List<List<String>> group(Map<String, List<String>> map) {    List<List<String>> output = new ArrayList<>();    if (map == null || map.isEmpty()) {        return output;    }    Map<String, List<String>> holder = new HashMap<>();    for (Map.Entry<String, List<String>> entry : map.entrySet()) {        String key = entry.getKey();        List<String> value = entry.getValue();        for (String v : value) {            if (!holder.containsKey(v)) {                holder.put(v, new ArrayList<String>());            }            holder.get(v).add(key);        }    }    return new ArrayList<List<String>>(holder.values());}

Answer 1

我们可以使用图论对这种方法进行实际的复杂性估计。“连接组件”方法将具有复杂性，其中是所有成分和菜肴的集合，并且是包含所有关系的集合，其中每个都是一道菜并且是菜肴的成分 。（即假设您将此图存储在邻接列表中，而不是邻接矩阵中）O(|V| + |E|)VE(a, b)abbG = (V, E)

在任何需要找出每道菜的所有成分才能找到结果的算法中，您都必须调查每道菜及其所有成分。这将导致需要时间的调查（即遍历），这意味着没有这样的算法可以比您的方法更好。O(|V| + |E|)

Answer 2

让我们首先把这个问题变成一个图形问题。每道菜和每种成分都将是一个.菜肴和配料之间的每个关系都将是.vertexedge

让我们分析一下解决方案的最大大小。假设总体上有菜肴和配料，则最大溶液输出是当每道菜都相关时。在这种情况下，输出的大小，因此这是您可以实现的时间复杂度的下限。我们可以很容易地创建一个输入，我们必须迭代所有顶点和边，因此时间复杂度的另一个下限是 。此外，我们必须保存所有顶点和边，因此空间复杂性的下限也是如此。NMN^2N * MM * N

现在，让我们分析一下您的解决方案。您迭代所有菜肴=，对于每个菜肴，您迭代所有值=，并与您一起检查字典中是否如此。你的空间复杂性也是如此。我会说你的解决方案很好。NMO(1)O(N * M)O(M * N)

Answer 3

让我们首先把这个问题变成一个图形问题。每道菜和每种成分都将是一个.菜肴和配料之间的每个关系都将是.vertexedge

让我们分析一下解决方案的最大大小。假设总体上有菜肴和配料，则最大溶液输出是当每道菜都相关时。在这种情况下，输出的大小，因此这是您可以实现的时间复杂度的下限。我们可以很容易地创建一个输入，我们必须迭代所有顶点和边，因此时间复杂度的另一个下限是 。此外，我们必须保存所有顶点和边，因此空间复杂性的下限也是如此。NMN^2N * MM * N

现在，让我们分析一下您的解决方案。您迭代所有菜肴=，对于每个菜肴，您迭代所有值=，并与您一起检查字典中是否如此。你的空间复杂性也是如此。我会说你的解决方案很好。NMO(1)O(N * M)O(M * N)

Answer 4

你只需要在这里建立一个反向地图。

我认为你可以通过使用Java8中引入的API以更富有表现力的方式编写代码。Stream

基本步骤：

• 从地图中提取所有成分

• 对于每种成分，获得一组菜肴，您将拥有许多这样的集合 - 将所有此类集合收集到一个集合中 - 因此该方法的返回类型变为Set<Set<String>>

以下是实现：

private static Set<Set<String>> buildReverseMap(Map<String, Set<String>> map) {

    // extracting all the values of map in a Set

    Set<String> ingredients = map.values()

            .stream()

            .flatMap(Set::stream)

            .collect(Collectors.toSet());

    return ingredients.stream()

            // map each ingredient to a set

            .map(s ->

                    map.entrySet()

                            .stream()

                            .filter(entry -> entry.getValue().contains(s))

                            .map(Map.Entry::getKey)

                            .collect(Collectors.toSet())

            ).collect(Collectors.toSet());

}

时间复杂度分析：

假设你有菜肴和配料，在最坏的情况下，每个Dest可以有每种成分。对于每种成分，您需要迭代每道菜，并检查它是否包含当前成分。这种检查可以摊销完成，因为我们可以为每道菜提供配料。NMO(1)HashSet<String>

因此，对于每种成分，您将迭代每道菜，并检查该菜肴是否包含该成分。这给出了要摊销的时间复杂性。O(1)O(M*N)

空间复杂性分析：

就像在最坏的情况下一样，你可以让每个dist都由每种可用的成分组成。O(M*N)

注意：

您可以返回 ，而不仅仅是通过更改为List<Set<String>>Set<Set<String>>.collect(Collectors.toSet()).collect(Collectors.toList())