leetcode-python-合并两个有序数组
今天第一次电话面试，有点紧张，所以自己感觉表现的不是很好，面试过程中面试官问到了两个算法题，都是leecode上面的题目，而且我都做过，但是当时一下子都想不起来，回答的方法也都是比较傻的方法，尤其是合并两个有序数组的题目，在上个月15日做过，但是今天面试没能好好回答。
以后做leetcode的算法题目的时候，需要将当时解题的思路也要记录，而不是只把题目上传就好。
先看看合并两个有序数组的题目：
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
虽然可以将两个数组加起来，然后进行排序，但是这么做的话，就浪费了两个有序数组这个条件，可以通过归并排序的方式进行合并。
先说说这个题的解题思路以及流程，先看下面的两个列表：
meage_sort.png
如上图的两个列表，先创建一颗空列表m，接着对比指针i，j指向的两个元素的大小，将小的元素append到列表m中，然后把对应的指针加1，重复此步骤，直到某一个指针超出列表索引，将另一个列表中剩下的元素添加到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]
# 重复上面的步骤直到某个指针大于索引，将另一个列表中剩下的元素添加到m中
下面我们用代码来实现：
def merge_sort(nums1, nums2):
m = []
i, j = 0, 0
l_1, l_2 = len(nums1)-1, len(nums2)-1
# 当i，j的索引位置小于等于索引最大值的时候
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()来进行，只比较每个数组的第一位就可以，每次将两者小的一个数弹出添加到新的列表中，直到有一个列表为空：
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
这种方法其实和上面的思路一样，只是实现方式不同而已。
