leetcode 88 Merge Sorted Array

bbbbbb 发布于2019-08-15 13:39 / 2095人阅读

摘要：题目假设数组的长度大于需要排序的元素数量数组的后位为。解法看到这道题时一种常规思路可能是，从头遍历两个数组，将的元素插入到的合适的位置。

题目详情

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

题目的意思是，输入两个已经排好序的数组nums1和nums2，要根据顺序把nums2种的元素并入nums1数组中。其中，nums1数组的待排序元素数量为m，nums2数组的待排序元素数量为n。题目假设nums1数组的长度大于需要排序的元素数量（数组的后n位为0）。

解法

看到这道题时一种常规思路可能是，从头遍历两个数组，将nums2的元素插入到nums1的合适的位置。但是在这道题里，数组的插入会导致大量的工作量。

同时我们注意到，nums1数组的后n个位置都是可以被利用的，同时对于这些位置元素的改变并不会影响nums1数组前面待排序的元素。

所以我们从最大的待排序元素进行判断，将最大的元素赋值给nums1的最后一个元素...以此类推

如果nums1的元素全部排序完毕，nums2的元素还有剩余，那么我们要将nums2数组剩下的元素插入nums1数组中。如果nums2数组先被排序完毕，那么就直接得到了最后的结果。

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        int i = m-1;
        int j = n-1;
        int k = m+n-1 ;
        
        while(i >= 0 && j >= 0 ){            
            if(nums1[i] > nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
        
        while(j >= 0){
            nums1[k--] = nums2[j--];
        }
        
        
    }

这道题的描述不是很清晰，如果理解了，想法还是比较简单的～

服务器托管云服务器 sorted-array array_merge() array_merge Sorted

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

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

leetcode88 Merge Sorted Array

摘要：题目要求将两个有序数组合并至其中一个数组并且该新数组仍然有序。所以我们可以换一种思维方式，从大至小遍历，这样可以将较大的元素直接填入当前的位置而且不用考虑移动其它的元素。题目要求 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: You...

taohonghui 2019-08-14 18:36 评论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