假設您有兩個整數串列：[1,2,8] 和 [3,6,7]。如果預算為 6，則回傳的 int 必須為 5 (2 3)。我正在努力尋找比 n^2 更快的解決方案。問題的第二部分是“如果串列的數量不固定，您將如何更改您的功能？” 如，有多個串列，串列存盤在二維陣列中。任何指導或幫助將不勝感激。
uj5u.com熱心網友回復：
我將為 2 個序列的情況提供答案。您需要針對擴展案例提出單獨的問題。我假設條目是自然數（即沒有負數）。
將您的值存盤在NavigableSet. 此介面的實作（例如TreeSet）允許您有效地找到（例如）小于數量的最大值。
因此，如果您將 2 套中的每一套都放在 a 中，NavigableSet那么您可以使用：
set1.headSet(total).stream()
.map(v1 -> Optional.ofNullable(set2.floor(total - v1)).map(v2 -> v1 v2)
.flatMap(Optional::stream)
.max(Integer::compareTo);
本質上，這會流式傳輸第一個集合中小于總數的所有元素，然后找到第二個集合中小于總數的最大元素 - 元素（如果有的話），將它們相加并找到最大的元素。如果沒有這樣的元素，它會回傳一個Optionalwhich is 。empty
您不一定需要將第一個集合設為 a NavigableSet- 您可以使用任何排序結構，然后用于Stream.takeWhile僅查看小于目標的元素。
一旦構建了集合，這應該是 O(n * log n)。通過導航第二組而不是使用floor.
uj5u.com熱心網友回復：
我認為我的第一種方法是使用 for 陳述句并將元素添加到下一個陣列的每個中，然后取接近預算但不超過預算的任何內容。我是java新手，但我沒有得到你的解決方案，所以我不知道這是否有幫助。
對于您問題的第二部分，您是指陣列的無限長度嗎？如果是這樣，您可以為此使用 ArrayList。
uj5u.com熱心網友回復：
如果有多個串列，解決該問題的最佳方法是使用哈希表來存盤總和為您想要的數字（預算）的值對或值序列。
您只需列印出與數字相加的哈希映射鍵和值（鍵是整數，值：整數串列）。
時間復雜度 O(N) 其中 N 是最大串列的大小，空間復雜度為 O(N)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/472645.html