三指针

题目

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

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例1：

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

示例2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

题解

思路

由于两个数组已经有序，所以两个指针控制m-1和n-1处值，比较两者并将其复制值m+n-1处，当比较一次，m+n-1处前移一次。故需要三个指针指向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def merge(self, nums1, m, nums2,n) -> None: # nums1：List[int]，nums2:List[int]
        """
        Do not return anything, modify nums1 in-place instead.
        """
        pos = m+n-1
        m -=1
        n -=1
        while m>=0 and n>=0:
            #print(pos,m,n,nums1[m],nums2[n])
            if nums1[m]>nums2[n]:
                nums1[pos]=nums1[m]
                m -=1
            else:
                nums1[pos]=nums2[n]
                n -=1
            pos -=1
            #print("dddd",nums1)
        while n>=0:
            nums1[pos]=nums2[n]
            pos -=1
            n -=1
        return nums1
1
2
3
4
5
6
7
a= Solution()
nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
result = a.merge(nums1,m,nums2,n)
print(result)
5 2 2 3 6
dddd [1, 2, 3, 0, 0, 6]
4 2 1 3 5
dddd [1, 2, 3, 0, 5, 6]
3 2 0 3 2
dddd [1, 2, 3, 3, 5, 6]
2 1 0 2 2
dddd [1, 2, 2, 3, 5, 6]
[1, 2, 2, 3, 5, 6]
1
2
3
4
5
6
7
a= Solution()
nums1 = [0]
m = 0
nums2 = [1]
n = 1
result = a.merge(nums1,m,nums2,n)
print(result)
[1]
1
2
3
4
5
6
7
nums1 = [1]
m = 1
nums2 = []
n = 0
a =Solution()
result =a.merge(nums1,m,nums2,n)
print(result)
[1]

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2021/02/01/LeetCode-E-%E5%8F%8C%E6%8C%87%E9%92%88-88.%20%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84/