你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

【LeetCode】第88题:合并两个有序数组

2021/12/6 5:04:42

 题目:

给两个有序的整数数组nums1和nums2,另有两个整数m和n,分别表示nums1和nums2中的元素数目

请合并nums2到nums1 中,使合并后的数组同样有序排列

注意:合并后的数组不应由函数返回,而是存储在数组nums1中,假设nums1的初始长度为m+n,其中前m个元素表示应合并的元素,后n个元素为0,nums2的长度为n

题目链接:合并两个有序数组


题目限制:

合并后同样以递增顺序排序

nums2合并到nums1后面

设计实现一个时间复杂度为O(m+n)的算法


解题思路:

思路一:合并后重新排序

时间复杂度为O((m+n)log(m+n))

空间复杂度为O(log(m+n))

思路二:复制数组一,利用双指针排序遍历到nums1中

p1指针复制nums1,p2指针遍历nums2

比较p1和p2指针的元素大小,按从小到大装进nums1,覆盖里面的函数

因为题目给出m为nums1的元素数量,nums1初始长度为m+n,实际元素只有m个,其余皆为0(n个,且应忽略)

受已排序条件影响,nums1数组中的元素已有序排列,且m个元素后使用0填充

实际可理解为nums1数组长度只有m,元素也只有m个

因此,p1在遍历复制的nums1过程中,无需考虑m个元素后存在p2与nums1中的m个元素后的0比较问题

但该思路缺点在于nums1和nums2都需要全部遍历才能结束

因此,时间复杂度为O(m+n),空间复杂度为O(m+n)

思路三:双指针逆向遍历在nums1中排序合并

在思路二的基础上,取消临时数组,结合nums1初始长度为m+n的特点,使用双指针的方式一边逆向遍历nums2,一边将比较的元素添加到nums1中

设p1、p2为nums1、nums2最后一位元素

在遍历过程中的任意时刻:

nums1数组中有m-1-p1个元素被放入nums1的后半部分

nums2数组中有n-1-p2个元素被放入nums1的后半部分

在指针p1后面,nums1数组有m+n-p1-1个位置,则有

m + n - p1 - 1 ≥ m - 1 - p1 +  n - p2 - 1

转换得:p2 ≥ -1

可证明p1后面永远足够容纳被插入的元素,不会产生nums1元素被覆盖的情况


数组边界:

nums1.length == m+n

nums2.length == n

m + n - p1 - 1 ≥ m - 1 - p1 +  n - p2 - 1


实现代码:

思路一:暴力合并

# 思路一
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.
        """
        nums1[m:] = nums2                   # 切片到m元素之后的元素等于nums2的元素
        nums1.sort()                        # 因为只是合并而已,仍需重新排序

思路二:双指针

# 思路二
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:                             # nums1完全遍历时,只剩下nums2的元素未遍历
                sorted.append(nums2[p2])            # 因为nums2为有序排序,则只需要不断添加nums2的元素即可
                p2 += 1
            elif p2 == n:                           # nums2完全遍历时,只剩下nums1的元素未遍历
                sorted.append(nums1[p1])            # 因为nums1为有序排序,则只需要不断添加nums1的元素即可
                p1 += 1
            elif nums1[p1] < nums2[p2]:             # 比较两个数组元素且nums2当前元素较大时
                sorted.append(nums1[p1])
                p1 += 1
            else:                                   # 比较两个数组元素且nums1当前元素较大时
                sorted.append(nums2[p2])
                p2 += 1
        nums1[:] = sorted                           # sorted数组为所求数组,仅需将nums1等于sorted即可

思路三:官方代码

# 思路三 官方代码

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.
        """
        p1, p2 = m - 1, n - 1                       # 设p1、p2为两个数组的最后一位有效元素
        tail = m + n - 1                            # 设tail为nums1最后一位元素
        while p1 >= 0 or p2 >= 0:                   # 若条件不成立,则已遍历完成
            if p1 == -1:                            # 当nums1数组全部遍历后
                nums1[tail] = nums2[p2]             # 仅需添加nums2的元素即可
                p2 -= 1
            elif p2 == -1:                          # 当nums2数组全部遍历后
                nums1[tail] = nums1[p1]             # 仅需添加nums1的元素即可
                p1 -= 1
            elif nums1[p1] > nums2[p2]:             # nums1元素比nums2大时
                nums1[tail] = nums1[p1]
                p1 -= 1
            else:                                   # nums2元素比nums1大时
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1                               # 触发条件后,tail逆向移动一位

若难以理解,可通过观看官方解说视频或执行以下代码逐步观察其代码逻辑

Python Tutor - Visualize Python, Java, JavaScript, C, C++, Ruby code execution

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

class Solution:
    def plusOne(self, nums1,nums2):
        p1, p2 = m - 1, n - 1
        tail = m + n - 1
        while p1 >= 0 or p2 >= 0:                   # 若条件不成立,则已遍历完成
            if p1 == -1:                            # 当nums1数组全部遍历后
                nums1[tail] = nums2[p2]             # 仅需添加nums2的元素即可
                p2 -= 1
            elif p2 == -1:                          # 当nums2数组全部遍历后
                nums1[tail] = nums1[p1]             # 仅需添加nums1的元素即可
                p1 -= 1
            elif nums1[p1] > nums2[p2]:             # nums1元素比nums2大时
                nums1[tail] = nums1[p1]
                p1 -= 1
            else:                                   # nums2元素比nums1大时
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1                               # 触发条件后,tail逆向移动一位
        return nums1

if __name__ == '__main__':
    s = Solution()
    S = s.plusOne(nums1,nums2)
    print(S)

思路三:简化循环

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1, p2 = m - 1, n - 1
        tail = len(nums1) - 1
        while p2 >= 0:
            if p1 < 0 or nums1[p1] <= nums2[p2]:
                nums1[tail] = nums2[p2]
                p2 -= 1
            else:
                nums1[tail] = nums1[p1]
                p1 -= 1
            tail -= 1

结论:

思路二是正向双指针遍历,其中最后的nums[:] = sorted 而不是用nums1 = sorted 是因为nums1 = sorted是赋值,只改变形参,未改变实参的内存

思路二倒过来就是思路三了,利用已排序的条件和nums1初始长度为m + n,可减少临时变量的参数,直接修改nums1


LeetCode相关数组题:

【LeetCode】第66题:加一_inganxu-CSDN博客

【leecode】第53题:最大子序和_inganxu-CSDN博客

【leecode】第35题:搜索插入位置_inganxu-CSDN博客

【leecode】第27题:移除元素_inganxu-CSDN博客

【leecode】第1题:两数之和_inganxu-CSDN博客