如何將兩個有序數組合併到一個有序數組中，但不使用第三個數組

Question

給定兩個有序數組，按升序排列，其中一個數組保留額外的空間以容納兩個數組的所有元素，合併兩個有序數組，結果數組也按升序排序而不創建第三個數組。

我寫了一個合併程序，但我用了第三個數組。

Answer 1

如果您沒有效率問題，只需將一個數組添加到其他數組的末尾即可。然後對這個連接的數組進行排序。

Answer 2

public static int[] merge(int[] a, int[] b) {  
    int a_size = a.size(); 
    for(int i=0; i<b.size();i++) { 
     a[a_size]= b[i]; 
     a_size++; 
    } 
    Arrays.sort(a); 
} 

Answer 3

一種方法可以如下。

1. 從您的較小陣列中取出第一個元素，並在較大陣列中找到它的位置（說它是第n個位置）。

2. 現在從您的較小陣列中獲取第二個元素，並找到它在較大陣列中的位置，而不是從開始而不是從第n個位置開始。

3. 現在從更小的陣列中取第三個元素並重復此過程，直到您的較小陣列耗盡。

複雜性比較

1.Its最好的情況下是複雜低至較小陣列的大小。儘管最壞的情況是更大陣列的更小陣列尺寸。

2.如果使用Collection API即Collection.sort（）或Arrays.sort（）的實用程序排序方法，則其複雜度在每種情況下都爲O（nlogn），其中n = size由於這些方法使用合併排序。