leetcode88 Merge Sorted Array

taohonghui 发布于2019-08-14 18:36 / 2650人阅读

摘要：题目要求将两个有序数组合并至其中一个数组并且该新数组仍然有序。所以我们可以换一种思维方式，从大至小遍历，这样可以将较大的元素直接填入当前的位置而且不用考虑移动其它的元素。

题目要求

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

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

将两个有序数组合并至其中一个数组并且该新数组仍然有序。

思路和代码

一般的合并数组，我们会考虑利用一个新数组，并用两个指针分别遍历并顺序比较两个数组的元素，将较小的那个那个元素添加至结果数组之中。
但是此时我们需要将两个数组合并至已存在的一个数组之中，如果还是按照那种方法，我们需要在插入元素之后将当前的元素顺序后移，这回带来巨大的性能损耗。所以我们可以换一种思维方式，从大至小遍历，这样可以将较大的元素直接填入当前的位置而且不用考虑移动其它的元素。这种方法的时间复杂度为O(m+n)
代码如下：

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        //nums1的指针
        int pointer1 = m-1 ;
        //nums2的指针
        int pointer2 = n-1 ;
        for(int j = m+n-1 ; pointer1>=0 && pointer2>=0 && j>pointer1 ; j--){
            if(nums2[pointer2] >= nums1[pointer1]){
                nums1[j] = nums2[pointer2--];
            }else{
                nums1[j] = nums1[pointer1--];
            }
        }
        //将剩余的nums2中的元素填入nums[1]
        while(pointer2>=0){
            nums1[pointer2] = nums2[pointer2];
            pointer2--;
        }
    }

总之，挺简单的一道题

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 sorted-array array_merge() array_merge Sorted

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67119.html

leetcode 88 Merge Sorted Array

摘要：题目假设数组的长度大于需要排序的元素数量数组的后位为。解法看到这道题时一种常规思路可能是，从头遍历两个数组，将的元素插入到的合适的位置。题目详情 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. 题目的意思是，输入两个已经排好序的数组nums1和nu...

bbbbbb 2019-08-15 13:39 评论0 收藏0
leetcode部分题目答案之JavaScript版

摘要：自己没事刷的一些的题目，若有更好的解法，希望能够一起探讨项目地址自己没事刷的一些LeetCode的题目，若有更好的解法，希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LintCode/LeetCode] Merge Sorted Array

Problem Given two sorted integer arrays A and B, merge B into A as one sorted array. Notice You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements ...

summerpxy 2019-08-14 15:41 评论0 收藏0
[Leetcode] Merge Sorted Array 合并数组

摘要：但是如果我们从后往前，合并到第一个数组的最后，则不用位移。注意将和都先减，用和来代表下标，避免两个数组为空时抛出空指针异常。 Merge Sorted Array 最新更新请见：https://yanjia.me/zh/2019/02/... Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1...

quietin 2019-08-14 12:26 评论0 收藏0