算法方法建議 - 按順序合併兩個數組

我在與C＃相關的一次採訪中被問到了這一點。有2個陣列 - 從最低到最高排序。我需要將所有這些組合在第三個數組中，並且應該按照排序的方式插入它們（因爲它們正在進入）。算法方法建議 - 按順序合併兩個數組

我提到的解決方案是如下：

爲了討論起見讓我們說Array 1具有以下元素 - 1,2,3,4,5和Array 2具有以下元素 - 6,7,8,9,10
由於2個數組是預-sorted - 將Array 1的第一個元素與Array 2的第一個元素進行比較，並在Array 3中插入較低的元素。
你會那麼做同樣的Array 1Element 2和Array 2Element 1和流行在未來數最小

，我提到應該工作的方法 - 但我的問題如下：

這是最有效的方法嗎？
是否有技術術語（如Binary Search Algo等）可以描述這個過程？
解決此問題的任何其他指針？

來源

2013-03-21 Patrick

啊，這是歸併的歸併部分。 – 2013-03-21 20:34:45

是的，這是最有效的方法。

它運行在O(n)（其中n是兩個數組的大小），這意味着要通過數組一次。

爲了創建第三個數組，您將不得不經過每個元素一次（即使它只是以正確的順序將其添加到第三個數組）。

該過程通常被稱爲merge，它是Merge Sort算法的一部分。

Here is an implementation在這裏堆棧溢出。

來源

2013-03-21 20:34:00

本傑明 - 感謝這有助於很多。剛剛看了維基百科上的一個可視化文件 - http://en.wikipedia.org/wiki/Merge_sort，現在已經很清楚了。是否有我應該知道的常見算法 - C＃視角和麪試視角。任何指針都會幫助 – Patrick 2013-03-21 20:39:25

@Patrick這是一個非常寬泛的問題。根據我的經驗，人們喜歡詢問二叉樹算法（構建樹，avl樹，刪除節點），排序（合併排序，快速排序，堆排序），動態算法（請參閱「谷歌多邊形」。這實際上取決於你面試的位置，我最好的建議是在面試問題上閱讀很多內容，並且一般做很多面試。如果你在面試過程中獨自完成了這項工作，重做OK :)如果這個答案解決了你的問題，請考慮接受它。 – 2013-03-21 20:42:14

是的 - 在來回訪問後，在面試過程中完成了:)。等待時間過期說接受這個答案。非常感謝 – Patrick 2013-03-21 20:44:56

1）這是最有效的方法，O（n + m）。其中n是第一個數組的大小，m是第二個數組的大小。 2）它被稱爲合併排序算法的合併例程。

實際上，您可以合併2個以上的數組，通常在External sorting中使用或者當您有空間限制時。

來源

2013-03-21 20:36:33 Andrew

如果你知道輸入數組進行排序，然後合併算法是線性（O（N）的大O符號）。但是，如果您還知道其中一個陣列的最大值低於另一個陣列的最小值，則可以使用Array.Copy而不是比較單個元素以獲得更好的性能。
是的，這是一個merge algorithm。
練習使完美。我喜歡通過解決Project Euler問題來獲得樂趣 - 它們是「小」的，但是一旦你經歷了前幾個，他們會真的讓你思考如何解決它。

編輯的天賦：

來源

2013-03-21 20:37:20

謝謝。我舉了一個例子，其中數組1的元素（以排序的方式）比數組2小。但這是一個簡單的假設。合併排序看起來像一個完美的答案 - 只是我不知道名稱 – Patrick 2013-03-21 20:41:12

算法方法建議 - 按順序合併兩個數組

回答

相關問題