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

心已赠人 2023-06-03 11:56 13阅读 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
                        p-=1
    else:
    　　　　　　　　　　# p1<0,代表1的数字都已经从后往前比较完了，这时候只要把2中的数字一个个添加到合并后的数组就好了
                    nums1[p] = nums2[p2]
                    p-=1
                    p2-=1
            return nums1

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