我有兩個 ArrayList，例如：ArrayList a = new ArrayList(); a.add(10); a.add(35); a.add(51);ArrayList b = new ArrayList(); b.add(24); b.add(46); b.add(81);我需要創建一個函數，它將元素從 B 到 A 放入排序查詢中。（在我看來，它必須檢查 A 和 B 中相同位置的元素，并在 10 和 35 之間放置 24，在 35 和 51 之間放置 46，最后一個是 81）。我有： public static void merge(ArrayList a, ArrayList b) { a.addAll(b); Collections.sort(a); }但它不是一個有效的算法（N^2）。有沒有更有效的方法？
2 回答
不負相思意
TA貢獻1777條經驗 獲得超10個贊
從文檔 List.sort
這種實現是一種穩定的、自適應的、迭代的歸并排序，當輸入數組部分排序時，它需要的比較次數遠少于 n lg(n) 次，同時在輸入數組隨機排序時提供傳統歸并排序的性能。如果輸入數組幾乎已排序，則實現需要大約 n 次比較。臨時存儲要求從幾乎排序的輸入數組的小常量到隨機排序的輸入數組的 n/2 個對象引用不等。
這個實現的復雜度是 O(n lg(n))。大多數情況下甚至更低，尤其是在輸入幾乎已排序的情況下。Java 版本之間的復雜性可能會有所不同，但 O(n lg(n)) 非?？煽?。
回到你的算法，我們可以說
a.addAll(b); // requires O(n) Collections.sort(a); // requires O(n lg(n))
所以它永遠不會比 O(n lg(n)) 更糟。
拉丁的傳說
TA貢獻1789條經驗 獲得超8個贊
正如您所說，這兩個列表已排序，然后有一種 O(N) 方法來合并這兩個列表。
static List<Integer> merge(List<Integer> a, List<Integer> b) {
List<Integer> merged = new ArrayList<>(a.size() + b.size());
int ai = 0, bi = 0;
while (ai < a.size() && bi < b.size()) {
if (a.get(ai) < b.get(bi))
merged.add(a.get(ai++));
else
merged.add(b.get(bi++));
}
while (ai < a.size())
merged.add(a.get(ai++));
while (bi < b.size())
merged.add(b.get(bi++));
return merged;
}
添加回答
舉報
0/150
提交
取消