LeetCode 88. 合并两个有序数组 Merge Sorted Array

简介: LeetCode 88. 合并两个有序数组 Merge Sorted Array

LeetCode 88. 合并两个有序数组 Merge Sorted Array


Table of Contents

一、中文版

二、英文版

三、My answer

四、解题报告


一、中文版

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

 

说明:

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


二、英文版

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
Output: [1,2,2,3,5,6]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


三、My answer

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.
        """
        l = m + n
        while m > 0 and n > 0:
            if nums1[m-1] > nums2[n-1]:
                nums1[l-1] =  nums1[m-1]
                m -= 1
            else:
                nums1[l-1] = nums2[n-1]
                n -= 1
            l -= 1
        if n > 0:
            for i in range(n):
                nums1[i] = nums2[i]
        print(nums1)
        return nums1
"""
[1,2,3,0,0,0]
3
[2,5,6]
3
[1,2,0,0,0]
2
[2,5,6]
3
[2,5,6,0,0,0]
3
[1,2,3]
3
[2,5,6,0,0,0]
3
[5,7]
2
"""


四、解题报告

代码中注释部分是测试用例,LeetCode中我比较喜欢的一点就是可以同时测试多个,目前 lintcode 还不支持。

本算法算是一种逆向思维 —— 从后往前填满数组,而不是从前往后排,因为这样会遍历和移动多次数据,而从后往前只需要遍历 nums1 nums2 各一次。

比较 nums1 nums2 的数,谁大就放在所需位置,并向前移动一位指针。

如果最后剩的是 nums1 没遍历完,即 nums2 已全部插入 nums1 中,则不需要做任何操作,因为本来就是在 nums1 中的,剩下没遍历到的也是 nums1 的数。

但如果是剩的是 nums2,则说明原来的 nums1 已不在原位,需要把剩余的 nums2 的数填补到 nums1 的开头(因为从后往前遍历,剩下的位置是靠前的位置.)

相关文章
|
2月前
leetCode(删除有序数组中的重复项)
如何在不使用额外空间的情况下,通过双指针法原地删除有序数组中的重复项。
36 2
|
4月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
2月前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
40 0
|
4月前
|
算法
LeetCode第26题删除有序数组中的重复项
这篇文章介绍了LeetCode第26题"删除有序数组中的重复项"的解题方法,通过使用双指针技巧,高效地去除数组中的相邻重复元素。
LeetCode第26题删除有序数组中的重复项
|
4月前
|
算法
LeetCode第80题删除有序数组中的重复项 II
文章介绍了LeetCode第80题"删除有序数组中的重复项 II"的解法,利用双指针技术在O(1)空间复杂度内原地删除重复元素,并总结了双指针技术在处理有序数组问题中的应用。
LeetCode第80题删除有序数组中的重复项 II
|
4月前
|
Python
【Leetcode刷题Python】977. 有序数组的平方
解决LeetCode "有序数组的平方" 问题的方法:使用Python内置的快速排序、直接插入排序(但会超时)和双指针技术,并给出了每种方法的Python实现代码。
23 1
【Leetcode刷题Python】977. 有序数组的平方
|
4月前
|
算法
LeetCode第88题合并两个有序数组
文章分享了LeetCode第88题"合并两个有序数组"的解法,通过从后向前的合并策略避免了数组元素的前移,使用三个指针高效地完成了合并过程。
|
4月前
|
Python
【Leetcode刷题Python】108. 将有序数组转换为二叉搜索树
LeetCode上108号问题"将有序数组转换为二叉搜索树"的Python实现,通过递归选取数组中间值作为根节点,构建高度平衡的二叉搜索树。
28 2
|
4月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
56 0
|
4月前
|
Python
【Leetcode刷题Python】26. 删除有序数组中的重复项
本文提供了一种使用快慢指针法在原地删除升序数组中重复元素的Python实现,返回删除后数组的新长度,同时保持元素的相对顺序。
46 0