leetcode88之合并两个有序数组

题目描述：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array

代码实现

 1 def merge(nums1, m, nums2, n):
 2     '''
 3     合并到nums1,使其成有序数组
 4     :param nums1:
 5     :param m:
 6     :param nums2:
 7     :param n:
 8     :return:
 9     '''
10 
11     for i in range(len(nums1) - m):
12         nums1.pop(-1)
13 
14     # nums1 = nums1[:m]  # 切片产生新的对象
15     nums1.extend(nums2[:n])
16     nums1.sort()
17     # nums1 = sorted(nums1) # sorted() 排序产生新的对象，调用sort()排序不会产生新的对象
18     return nums1
19 
20 
21 print("-------测试merge()---------")
22 nums1 = [1]
23 nums2 = []
24 m, n = 1, 0
25 res = merge(nums1, m, nums2, n)
26 print("res=", res)
27 
28 
29 def merge1(nums1, m, nums2, n):
30     '''
31     两个指针来实现融合排序
32     :param nums1:
33     :param m:
34     :param nums2:
35     :param n:
36     :return:
37     '''
38     p1, p2 = 0, 0  # p1指向nums1,p2指向nums2
39 
40     for i in range(len(nums1) - m):
41         nums1.pop(-1)
42 　　L=n
43     while p2 < n:
44         if nums2[p2] <= nums1[p1]:
45             # nums1.pop(-1)
46             # 将nums2[p2]元素插入nums1当前位置
47             nums1.insert(p1, nums2[p2])
48             p2 += 1
49             p1 += 1
50         else:
51             p1 += 1
52 
53         # p1指针已经指向末尾，此时p2中还有值没加进去
54         if p1 == L:
55             nums1.extend(nums2[p2:])
56             break
57 
58     return nums1
59 
60 
61 print("-------测试merge()---------")
62 nums1 = [1, 2, 3, 0, 0, 0]
63 nums2 = [2, 5, 6]
64 m, n = 3, 3
65 res = merge1(nums1, m, nums2, n)
66 print("res=", res)

输出

1 -------测试merge()---------
2 res= [1]
3 -------测试merge()---------
4 res= [1, 2, 2, 3, 5, 6]

总结：采用两种方法实现要求。方法1 思路很简单，就是合并数组，然后排序。但有几点问题需要注意。第一：根据题目要求，最后输出的是nums1,所以整个代码运行过程中nums1对象始终在变换，切记如切片操作、sorted()等操作均返回新的对象，不会改变nums1。而像调用函数等操作均是改变调用调用对象，如sort(),extend()等。

方法2 采用双指针来实现，但该方法仍存在问题，如官方测试用例nums1=[0],nums2=[1],m=0,n=1，不能运行通过。但对大部分测试例子可以通过。题目要求是将nums2中元素插入nums1中合适位置，因此将遍历nums2作为循环条件，即while p2<n条件。判断nums2当前元素和nums1元素大小，如果nums2[p2]<=nums1[p1],将nums2元素插入nums1当前位置，改变相应指针位置；否则改变p1指针位置。每次判断结束后，需要判断p1指针是否已经指向nums1末尾，若指向，跳出循环结束，否则继续循环。