LeetCode——合并两个有序数组【Python3】

红太狼 2022-03-30 15:48 154阅读 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]

**思路**：首先想到的思路是先从前向后找到位置，然后插入进去，这样可能需要将一些元素往后挪动一些位置，时间复杂度o(n\*n),但是记住遇到这种排好序的数组操作，时间复杂度一般为o(n),所以我们再仔细观察题目，发现nums1末尾的数字都相当于未定。如果从后向前查找位置，不就不需要挪动了嘛，只需要交换。

**代码**：

从前向后：

class Solution:
        def merge(self, nums1, m, nums2, n):
            """
            :type nums1: List[int]
            :type m: int
            :type nums2: List[int]
            :type n: int
            :rtype: void Do not return anything, modify nums1 in-place instead.
            """
            len1 = m
            len2 = n
            #num1最后一个有效的数字
            lent = m -1
            index1 = 0
            index2 = 0
            if n != 0: 
                while index1 < m+n and index2 < len2:
                    #如果num1大于num2，则将num2插入num1中
                    if nums1[index1] > nums2[index2]:
                        i = lent
                        while i >= index1:
                            nums1[i+1] = nums1[i]
                            i -= 1
                        nums1[index1] = nums2[index2]
                        index2 += 1
                        lent += 1
                    #判断剩余需要合并的num2都大于num1的元素
                    elif nums2[index2] >= nums1[lent]:
                        nums1[lent+1] = nums2[index2]
                        index2 += 1
                        lent += 1
                        index1 = lent -1
                    index1 += 1

从后向前:先把末尾的空位置填满，如果遍历完num2，则说明完成，如果没有遍历完num2就遍历完num1了，则需要将num2的元素填充到num1前面去

def merge(self, nums1, m, nums2, n):
            """
            :type nums1: List[int]
            :type m: int
            :type nums2: List[int]
            :type n: int
            :rtype: void Do not return anything, modify nums1 in-place instead.
            """
            if n !=0:
                index1 = m -1
                index2 = n-1
                lent = m + n - 1
                while index1 >=0 and index2 >= 0:
                    if nums1[index1] > nums2[index2]:
                        nums1[lent] = nums1[index1]
                        index1 -= 1
                        lent -= 1
                    else:
                        nums1[lent] = nums2[index2]
                        index2 -= 1
                        lent -= 1
                while index2 >= 0:
                    nums1[lent] = nums2[index2]
                    index2 -= 1;lent -= 1

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

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

相关阅读

相关 [LeetCode]合并两个有序数组

若return a < b;若return a> b;输出结果 : 1 2 3。换其他数据类型也可以的。

布满荆棘的人生/ 2024年04月24日 20:33/ 0 赞/ 48 阅读

相关 leetcode 88：合并两个有序数组(python)

题目给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和...

冷不防/ 2024年04月18日 22:39/ 0 赞/ 31 阅读

相关合并两个有序数组【leetcode】

1. 题目：给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你

短命女/ 2023年10月14日 23:16/ 0 赞/ 109 阅读

相关 LeetCode题目（Python实现）：合并两个有序数组

文章目录题目自己的想法算法实现执行结果复杂度分析双指针 / 从

野性酷女/ 2023年07月08日 15:27/ 0 赞/ 44 阅读

相关 leetcode 88. 合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums

客官°小女子只卖身不卖艺/ 2022年04月16日 06:38/ 0 赞/ 225 阅读

相关 LeetCode——合并两个有序数组【Python3】

题目：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和

红太狼/ 2022年03月30日 15:48/ 0 赞/ 155 阅读

相关 leetcode:88. 合并两个有序数组

题目: 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和

雨点打透心脏的1/2处/ 2022年03月18日 11:22/ 0 赞/ 242 阅读

相关 LeetCode-88. 合并两个有序数组

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

怼烎@/ 2022年03月15日 12:42/ 0 赞/ 229 阅读

相关 LeetCode----------------------合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2 的

爱被打了一巴掌/ 2021年12月10日 00:39/ 0 赞/ 337 阅读

相关【LeetCode】 88. 合并两个有序数组

<table> <tbody> <tr> <td><font>题目</font></td> </tr> </tbody> </table>

川长思鸟来/ 2021年06月10日 20:38/ 0 赞/ 513 阅读