【LeetCode】两个有序数组合成一个有序数组（NEW)

心已赠人 2023-06-03 11:56 38阅读 0赞

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

说明:

初始化 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]

解法1:

之前如果不考虑合并，空间上新增一个数组可以解决这个问题

解法2:

合并的解法，题目说把2合并到1，那么1的空间肯定大于2

思路

  1. 我们需要不断的把2中的数字插入到1中，直到2中的数字都插入到1中

  2. 2中的数字插入到1中需要注意有两种情况，一种是1，2两个数组始终做比较，一种是1的数组中数字都已比较完，这样直接把2中数字插入到1中就可以了class 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. “”” 　　　　　# 如果2为空，直接返回1 if n==0: return nums1 # p代表合并后的数组1的index p = m+n-1 　　　　 # p1代表合并前数组1的index p1 = m-1 　　　　 # p2代表数组2的index 　　　　 # p,p1,p2也可以理解为指针 p2 = n-1 　　　　　# 只要数组2还没合并完全就一直合并 while p2>=0: 　　　　　　　　# 如果数组1的数字都还没有与2的比较完 if p1>=0: if nums2[p2]>nums1[p1]: nums1[p] = nums2[p2] p2 -= 1 p-=1 else: nums1[p] = nums1[p1] p1 -= 1

    1.                  p-=1

    else:
    　　　　　　　　　　# p1<0,代表1的数字都已经从后往前比较完了，这时候只要把2中的数字一个个添加到合并后的数组就好了

    1.              nums1[p] = nums2[p2]
    2.              p-=1
    3.              p2-=1
    4.      return nums1

转载于:https://www.cnblogs.com/dreamyu/p/11403293.html

发表评论

表情：
评论列表 （有 0 条评论，38人围观）

还没有评论，来说两句吧...

相关阅读