专栏首页机器学习养成记LeetCode刷题DAY 22:合并两个有序数组

LeetCode刷题DAY 22:合并两个有序数组

难度:简单 关键词:双指针

⭐️⭐️⭐️

1

题目描述

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

2

题解

思路:双指针

设置两个指针分别指向两个数组的起始位置,依次比较大小,每次将最小值放入输出数组中。因为要建立一个数据存放结果或nums1,所以空间复杂度最小为O(m),时间复杂度则为O(m+n)。

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.        """        i = 0        j = 0        nums3 = nums1[0:m]        nums1[:] = []        while i<m and j<n:            if nums3[i]<=nums2[j]:                nums1.append(nums3[i])                i += 1            else :                nums1.append(nums2[j])                j += 1        if i<m:            nums1[i+j:]=nums3[i:]        if j<n:            nums1[i+j:]=nums2[j:]

进一步将空间复杂度从O(m)缩减至O(1),可考虑从右至左依次比较,每次将最大值从右边依次放入输出数组中,此时要增加一个指针记录放入的位置。时间复杂度依旧是为O(m+n)。

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.        """        i = m-1        j = n-1        z = m+n-1        while i>=0 and j>=0:            if nums1[i]<=nums2[j]:                nums1[z]=nums2[j]                j -= 1            else :                nums1[z]=nums1[i]                i -= 1            z -= 1        if j >= 0:            nums1[:j+1]=nums2[:j+1]


本文分享自微信公众号 - 机器学习养成记(chenchenwings),作者:三猫后端

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《无问西东》豆瓣短评分析

    《无问西东》讲述了四代人清华人,在矛盾与期待中不断找寻自我、砥砺前行的故事。上映后得到了广泛的关注,也引发了强烈的讨论。本文首先通过爬虫技术,从豆瓣上获得相关短...

    三猫
  • 图片相似度识别:dHash算法

    之前已经介绍了aHash算法的基本原理及python实现代码(图片相似度识别:aHash算法),本次来继续介绍图片相似度识别的另一常用哈希算法——dHash。

    三猫
  • 如何进行用户价值细分?RFM模型! Part 2 人群优惠敏感度案例

    在之前的文章中我们介绍了RFM模型的基本知识,主要是根据消费相关的三个维度通过聚类,对人群进行划分(回顾可戳如何进行用户价值细分?RFM模型!Part 1 基础...

    三猫
  • Leetcode Golang 88. Merge Sorted Array.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88935287

    anakinsun
  • LeetCode 88. 合并两个有序数组

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

    freesan44
  • 【专知-关关的刷题日记16】Leetcode 88. Merge Sorted Array

    题目 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as on...

    WZEARW
  • 88合并两个有序数组

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

    宇宙之一粟
  • [LeetCode]Merge Sorted Array 合并排序数组 [LeetCode]Merge Sorted Array 合并排序数组

    链接:https://leetcode.com/problems/merge-sorted-array/description/ 难度:Easy 题目:88...

    尾尾部落
  • 每天一道leetcode88-合并两个有序数组

    乔戈里
  • Q88 Merge Sorted Array

    Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one s...

    echobingo

扫码关注云+社区

领取腾讯云代金券