我正在研究以下問題：假設您有一個菜肴列表，其中每道菜都與配料列表相關聯(lián)。將具有常見成分的菜肴分組在一起。例如：輸入："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());}
4 回答
慕神8447489
TA貢獻1780條經(jīng)驗 獲得超1個贊
我們可以使用圖論對這種方法進行實際的復雜性估計?！斑B接組件”方法將具有復雜性，其中是所有成分和菜肴的集合，并且是包含所有關系的集合，其中每個都是一道菜并且是菜肴的成分 。（即假設您將此圖存儲在鄰接列表中，而不是鄰接矩陣中）O(|V| + |E|)VE(a, b)abbG = (V, E)
在任何需要找出每道菜的所有成分才能找到結果的算法中，您都必須調查每道菜及其所有成分。這將導致需要時間的調查（即遍歷），這意味著沒有這樣的算法可以比您的方法更好。O(|V| + |E|)
慕仙森
TA貢獻1827條經(jīng)驗 獲得超8個贊
讓我們首先把這個問題變成一個圖形問題。每道菜和每種成分都將是一個.菜肴和配料之間的每個關系都將是.vertexedge
讓我們分析一下解決方案的最大大小。假設總體上有菜肴和配料，則最大溶液輸出是當每道菜都相關時。在這種情況下，輸出的大小，因此這是您可以實現(xiàn)的時間復雜度的下限。我們可以很容易地創(chuàng)建一個輸入，我們必須迭代所有頂點和邊，因此時間復雜度的另一個下限是 。此外，我們必須保存所有頂點和邊，因此空間復雜性的下限也是如此。NMN^2N * MM * N
現(xiàn)在，讓我們分析一下您的解決方案。您迭代所有菜肴=，對于每個菜肴，您迭代所有值=，并與您一起檢查字典中是否如此。你的空間復雜性也是如此。我會說你的解決方案很好。NMO(1)O(N * M)O(M * N)
MMTTMM
TA貢獻1869條經(jīng)驗 獲得超4個贊
讓我們首先把這個問題變成一個圖形問題。每道菜和每種成分都將是一個.菜肴和配料之間的每個關系都將是.vertexedge
讓我們分析一下解決方案的最大大小。假設總體上有菜肴和配料，則最大溶液輸出是當每道菜都相關時。在這種情況下，輸出的大小，因此這是您可以實現(xiàn)的時間復雜度的下限。我們可以很容易地創(chuàng)建一個輸入，我們必須迭代所有頂點和邊，因此時間復雜度的另一個下限是 。此外，我們必須保存所有頂點和邊，因此空間復雜性的下限也是如此。NMN^2N * MM * N
現(xiàn)在，讓我們分析一下您的解決方案。您迭代所有菜肴=，對于每個菜肴，您迭代所有值=，并與您一起檢查字典中是否如此。你的空間復雜性也是如此。我會說你的解決方案很好。NMO(1)O(N * M)O(M * N)
慕妹3146593
TA貢獻1820條經(jīng)驗 獲得超9個贊
你只需要在這里建立一個反向地圖。
我認為你可以通過使用Java8中引入的API以更富有表現(xiàn)力的方式編寫代碼。Stream
基本步驟：
從地圖中提取所有成分
對于每種成分，獲得一組菜肴，您將擁有許多這樣的集合 - 將所有此類集合收集到一個集合中 - 因此該方法的返回類型變?yōu)?code>Set<Set<String>>
以下是實現(xiàn)：
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())
添加回答
舉報
0/150
提交
取消