LeetCode刷题笔记第88题：合并两个有序数组_给一个有序数组,如[1,2,3,5,7,9,10,12],将连续的元素合并,中间用‘-‘连接,返回字

LeetCode刷题笔记第88题：合并两个有序数组

想法一：
合并两个有序数组，先将两个数组合并成一个数组，然后对数组中的元素重新排序，得到合并的两个有序数组

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # 合并两个有序数组
        # 将nums2数组元素全部放入nums1的后面
        nums1[m:] = nums2
        # 返回nums1的重新排序
        return nums1.sort()
1
2
3
4
5
6
7
8
9
10

想法二：
创建一个列表存放两个有序数组的元素，通过有序数组的长度进行遍历，将较小元素优先排入列表，将列表中的元素赋值给nums1。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # 创建一个列表存放两个有序数组的元素
        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，题目需要nums1 in-place
        nums1[:] = sorted
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