88.合并两个有序数组
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
思路
- 归并
设置两个指针i,j,从头开始遍历两个数组，哪个指针指向位置的元素较小则加入结果列表中，该指针后移，…，依次类推。
如果两个数组长度不一样，循环结束后，需要将长度较长的数组剩余元素加入结果列表。 - 双指针
由于题目所给数组均有序，因此可以设置两个指针分别指向两个数组第一个元素，判断两个指针指向位置的元素大小，每次将较小的加入结果列表中。
如果某一个数组先遍历结束，后续只需要遍历另一个数组的剩余元素并将其加入结果列表中。 - 先将数组nums2放进数组nums1的尾部，然后直接对整个数组进行排序
- 逆向双指针
对双指针法进行改进，从后往前遍历数组，每次将较大元素放入结果列表中。
在双指针法中，我们需要创建长度为m+n的新数组保存结果，因为如果直接在nums1上保存，会覆盖nums1的元素。
与双指针方法不同的是，该方法可以原地地在nums1上保存结果（从后往前放入元素不会产生覆盖）。代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
归并
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
i = 0
j = 0
result = []
while i < m and j < n:
if nums1[i] < nums2[j]:
result.append(nums1[i])
i += 1
elif nums1[i] >= nums2[j]:
result.append(nums2[j])
j += 1
if m - i != 0:
for k in range(m - (m - i), m):
result.append(nums1[k])
if n - j != 0:
for p in range(n - (n - j), n):
result.append(nums2[p])
nums1[:] = result
def merge1(self, nums1, m, nums2, n):
# 先将数组nums2放进数组nums1的尾部，然后直接对整个数组进行排序
nums1[m:] = nums2
quick_sort(nums1, 0, len(nums1) - 1)
def merge2(self, nums1, m, nums2, n):
sorted = []
p1, p2 = 0, 0
while p1 < m or p2 < n:
if p1 == m:
sorted.append(nums2[p2])
p2 += 1
elif p2 == n:
sorted.append(nums1[p1])
p1 += 1
elif nums1[p1] < nums2[p2]:
sorted.append(nums1[p1])
p1 += 1
else:
sorted.append(nums2[p2])
p2 += 1
nums1[:] = sorted
def merge3(self, nums1, m, nums2, n):
"""逆向双指针"""
p1, p2 = m - 1, n - 1
tail = m + n - 1
while p1 >= 0 or p2 >= 0:
if p1 == -1: # 如果nums1数组已经遍历完毕，遍历nums2中的剩余元素
nums1[tail] = nums2[p2]
p2 -= 1
elif p2 == -1: # 如果nums2数组已经遍历完毕，遍历nums1中的剩余元素
nums1[tail] = nums1[p1]
p1 -= 1
elif nums1[p1] > nums2[p2]:
nums1[tail] = nums1[p1]
p1 -= 1
else:
nums1[tail] = nums2[p2]
p2 -= 1
tail -= 1
def quick_sort(arr, low, high):
"""快速排序"""
if low < high:
pivot = partition(arr, low, high)
quick_sort(arr, low, pivot - 1)
quick_sort(arr, pivot + 1, high)
def partition(arr, low, high):
pivot_key = arr[low]
while low < high:
while low < high and arr[high] >= pivot_key:
high -= 1
arr[low], arr[high] = arr[high], arr[low]
while low < high and arr[low] <= pivot_key:
low += 1
arr[low], arr[high] = arr[high], arr[low]
return low
if __name__ == "__main__":
slt = Solution()
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
# slt.merge(nums1, 3, nums2, 3)
# slt.merge1(nums1, 3, nums2, 3)
# slt.merge2(nums1, 3, nums2, 3)
slt.merge3(nums1, 3, nums2, 3)
print(nums1)
