leetcode-python-合并兩個(gè)有序數(shù)組
今天第一次電話面試庐舟，有點(diǎn)緊張，所以自己感覺(jué)表現(xiàn)的不是很好历帚，面試過(guò)程中面試官問(wèn)到了兩個(gè)算法題滔岳，都是leecode上面的題目谱煤，而且我都做過(guò)刘离，但是當(dāng)時(shí)一下子都想不起來(lái)睹栖，回答的方法也都是比較傻的方法，尤其是合并兩個(gè)有序數(shù)組的題目野来，在上個(gè)月15日做過(guò)曼氛，但是今天面試沒(méi)能好好回答。
以后做leetcode的算法題目的時(shí)候舀患，需要將當(dāng)時(shí)解題的思路也要記錄构舟，而不是只把題目上傳就好狗超。
先看看合并兩個(gè)有序數(shù)組的題目：
給定兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2，將 nums2 合并到 nums1 中努咐，使得 num1 成為一個(gè)有序數(shù)組渗稍。
雖然可以將兩個(gè)數(shù)組加起來(lái)竿屹，然后進(jìn)行排序，但是這么做的話拱燃，就浪費(fèi)了兩個(gè)有序數(shù)組這個(gè)條件，可以通過(guò)歸并排序的方式進(jìn)行合并父晶。
先說(shuō)說(shuō)這個(gè)題的解題思路以及流程弄跌，先看下面的兩個(gè)列表：
如上圖的兩個(gè)列表埠胖，先創(chuàng)建一顆空列表m淳玩，接著對(duì)比指針i凯肋，j指向的兩個(gè)元素的大小，將小的元素append到列表m中圈盔，然后把對(duì)應(yīng)的指針加1悄雅，重復(fù)此步驟，直到某一個(gè)指針超出列表索引众眨，將另一個(gè)列表中剩下的元素添加到m中娩梨。
a = [1,2,3,4,5,6]
b = [2,4,6,8,9,10]
m = []
i,j = 0,0
a[i] < b[j] # 1<2
m.append(a.pop(i)) # m=[1]
a[i] == b[j] # 2 == 2
m.append(a[i]) # m = [1, 2]
a[i] > b[j] # 3 > 2
m.append(b[j]) # m = [1, 2, 2]
# 重復(fù)上面的步驟直到某個(gè)指針大于索引览徒，將另一個(gè)列表中剩下的元素添加到m中
下面我們用代碼來(lái)實(shí)現(xiàn)：
def merge_sort(nums1, nums2):
m = []
i, j = 0, 0
l_1, l_2 = len(nums1)-1, len(nums2)-1
# 當(dāng)i，j的索引位置小于等于索引最大值的時(shí)候
while i <= l_1 and j <= l_2:
if nums1[i] <= nums2[j]:
m.append(nums1[i])
i += 1
else:
m.append(nums2[j])
j += 1
m = m + nums1[i:] + nums2[j:]
return m
if __name__ == '__main__':
n1 = [1, 2, 3, 4, 5]
n2 = [2, 4, 5, 6, 7]
m = merge_sort(n1, n2)
print(m)
# [1, 2, 2, 3, 4, 4, 5, 5, 6, 7]
我們也可以使用Python中的列表方法pop()來(lái)進(jìn)行习蓬，只比較每個(gè)數(shù)組的第一位就可以躲叼，每次將兩者小的一個(gè)數(shù)彈出添加到新的列表中枫慷，直到有一個(gè)列表為空：
def merge_sort(nums1, nums2):
m = []
i, j = 0, 0
while nums1 and nums2:
if nums1[i] <= nums2[j]:
temp = nums1.pop(i)
m.append(temp)
else:
temp = nums2.pop(j)
m.append(temp)
m = m + nums1 + nums2
return m
這種方法其實(shí)和上面的思路一樣包斑，只是實(shí)現(xiàn)方式不同而已。
