使用拼圖陣列

Question

我的第一陣列M + N的大小和尺寸N的第二陣列

讓我們說M = 4，N = 5
一個[] = 1,3,5,7,0， 0,0,0,0

b [] = 2,4,6,8,10

現在，我如何合併這兩個陣列，而無需使用外部的排序算法以及任何其它臨時數組（就地合併），但複雜性應該是o（n）。結果數組必須按排序順序。

Answer 1

提供的是完全正確的大小和數組已經排序（似乎是這樣），下面的僞代碼應幫助：

# 0 1 2 3 4 5 6 7 8 
a = [1,3,5,7,0,0,0,0,0] 
b = [2,4,6,8,10] 
afrom = 3 
bfrom = 4 

ato = 8 
while bfrom >= 0: 
    if afrom == -1: 
     a[ato] = b[bfrom] 
     ato = ato - 1 
     bfrom = bfrom - 1 
    else: 
     if b[bfrom] > a[afrom]: 
      a[ato] = b[bfrom] 
      ato = ato - 1 
      bfrom = bfrom - 1 
     else: 
      a[ato] = a[afrom] 
      ato = ato - 1 
      afrom = afrom - 1 
print a 

它基本上是將兩個列表合併爲一個，從末端開始。一旦bfrom達到-1，b中沒有其他元素，因此a中的餘數小於b中的最低值。因此a的其餘部分可以保持不變。

如果a用完第一，那麼它的，因爲所有的a元件上方ato已經被轉移轉移的b其餘的問題。

這是O（n）的要求，並會導致類似：

[1, 2, 3, 4, 5, 6, 7, 8, 10] 

---

應該理解的是僞代碼，並將其翻譯成特定語言適合你的工作，現在你已經宣佈它做作業:-)

Answer 2

for (i = 0; i < N; i++) { 
    a[m+i] = b[i]; 
} 

這將執行就地合併（拼接）。

如果您要求進行有序合併，那麼在O（N）中是不可能的。如果可能的話，你可以用它來排序O（N）。當然，O（N log N）是最着名的一般情況下的排序算法...

我不得不問，但看看你最後幾個問題：你只是要求我們幫助作業嗎？你知道可以說「這是家庭作業」，沒有人會嘲笑你，對吧？我們甚至會盡全力幫助您學習。

Answer 3

你想要一個排序的數組嗎？如果不是這應該做

for(int i=a.length-1,j=0;i >=0; i--) { a[i] = b[j++]; }

Answer 4

你可以看看in-place counting sort提供你知道輸入範圍的作品。有效O（n）。