python 面試題：兩個有序遞增數組合併後排序

題目：

  • 有兩個遞增的有序數組 如： list1 = [0,2,3,4,5,6,8,9 ...] list2 = [1,7,9,10,11 ...]

  • 將兩個數組合併后重新排序，保持遞增， 則輸出如： [0,1,2,3,4,5,6,7,8,9,9,10,11 ...]

感謝大家的評論，現給出幾種方案：

  • sorted 

sorted(list1+list2)

  • 歸併排序

Merge(list1, list2)

  • 忘記歸併排序的我...

  • 如果list2 中的第一個數字 >= list1 中的最後一個數字，則直接合併，list1+list2

  • 如果list1 中的 第一個數字 >= list2 中的最後一個數字，則直接合併， list2+list1

    Advertisements

  • 如果兩個list不能直接合併，則 倒序遍歷list1，從list1中最大的數開始，逐個插入到list2中

    1. 當插入過程中，發現插入在list2的最前方時，代表list1中剩餘的未插入數字都比list2中的小，則直接將list1中剩餘的未插入的部分合併到ist2的最前方，返回

    2. 如果沒有出現插入位置在最前方的情況，則依次插入，返回最後的list2

代碼：

執行時間短 至 長

sorted < 並歸 < 我

Advertisements

你可能會喜歡

Advertisements