美文网首页算法学习
算法题--合并有序数组

算法题--合并有序数组

作者: 岁月如歌2020 | 来源:发表于2020-04-25 16:07 被阅读0次
image.png

0. 链接

题目链接

1. 题目

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]

2. 思路1:逐个比较最后一个元素, 将大数放入nums1尾部

3. 代码

# coding:utf8
from typing import List


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


def my_test(solution, nums1, m, nums2, n):
    print('input: nums1={}, m={}, nums2={}, n={}'.format(nums1, m, nums2, n))
    solution.merge(nums1, m, nums2, n)
    print('output: {}'.format(nums1))


solution = Solution()
my_test(solution, [1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3)
my_test(solution, [2,0], 1, [1], 1)
my_test(solution, [1], 1, [], 0)


输出结果

input: nums1=[1, 2, 3, 0, 0, 0], m=3, nums2=[2, 5, 6], n=3
output: [1, 2, 2, 3, 5, 6]

input: nums1=[2, 0], m=1, nums2=[1], n=1
output: [1, 2]

input: nums1=[1], m=1, nums2=[], n=0
output: [1]

4. 结果

image.png

相关文章

  • 一道算法题之两个有序数组合并

    最近面试的时候遇到了一道算法题,两个有序数组合并,要求新的数组也是有序的 此题比较简单,主要是看数组元素进行对比,...

  • 算法题--合并有序数组

    0. 链接 题目链接 1. 题目 Given two sorted integer arrays nums1 an...

  • 88、合并两个有序数组 | 算法(leetcode,附思维导图

    零 标题:算法(leetcode,附思维导图 + 全部解法)300题之(88)合并两个有序数组 一 题目描述 二 ...

  • 对两个有序的数组进行合并

    1、算法描述: 有两个有序的整型数组arrayA,和arrayB,先要将它俩合并得到新的合并数组同样是有序的。示例...

  • 面试问题收集

    小米 1、算法题:合并两个排序数组成为一个有序数组 2、HashMap实现原理,自定义key的注意事项 3、has...

  • 归并排序

    原理:将原序列划分为有序的n个序列,然后利用归并算法进行合并,合并之后即为有序序列。要点:分治,归并 将数组arr...

  • iOS面试之算法大全

    算法 算法内容如下: 字符串反转 链表反转 有序数组合并 Hash算法 查找两个子视图的共同父视图 求无序数组当中...

  • iOS面试之算法模块

    算法 算法内容如下: 字符串反转 链表反转 有序数组合并 Hash算法 查找两个子视图的共同父视图 求无序数组当中...

  • 算法必知 --- 归并排序(优化与案例)

    算法描述 使用归并排序进行升序排列。 示例: 算法设计 基本思路:借助额外空间,合并两个有序数组,得到更长的有序数...

  • 合并两个有序数组(C)

    合并两个有序数组,合并完之后仍有序:

网友评论

    本文标题:算法题--合并有序数组

    本文链接:https://www.haomeiwen.com/subject/mhskwhtx.html