[leetcode-排序]--88. Merge Sorted Array

悠悠 2022-07-11 23:27 128阅读 0赞

Question 88. Merge Sorted Array

> Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
> 
> 中文： 给定两个有序的整型数组num1和num2，将num2合并进num1，成为一个新的数组。
> 
> 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.
> 
> 注意：我们可以假定nums1的空间足够大，完全可以把num2合并进num1。num1和num2初始化大小分别是m和n

解决思路：双指针法夹逼。因为num1和num2都是有序递增的，现在要把num2合并进num1，并且num1和num2的长度已知告诉我们了，这时候，如果我们从前往后比较，免不了要涉及到移动大量的数据，这是非常耗时间的，所以我们逆向思维，我们从后往前比较，然后从m+n-1 的位置开始存储（这么做有个前提，就是num1必须得确保有m+n-1这么大，本题目中，题目已经给定了。）。简单点说：就是从num1\[m-1\]和num2\[n-1\]开始比较，大的存储在最后，然后向前递推。

实现代码：

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m+n-1;//合并后最后一个元素的索引
        int ia = m-1;
        int ib = n-1;
    
        while(index >= 0){
            //num1已经遍历完了.将num2剩余数据存入num1中
            if(ia < 0){
                for(int i= ib; i>=0; i--){
                    nums1[index--] = nums2[ib--];
                }
                return;
            }
            //num2已经遍历完了.将num1剩余数据存入num1中
            if(ib < 0){
                //其实什么都不用做,直接return
                return;
            }
    
            //将较大的数字存储在最后.
            if(nums1[ia] > nums2[ib]){
                nums1[index--] = nums1[ia];
                ia--;
            }else {
                nums1[index--] = nums2[ib];
                ib--;
            }
        }
    }

比较简单的代码，上面的代码唯一需要注意的是，要将ia和ib的判断放在循环的前面，否则就可能会出现当nums1或则nums2本身为空数组时，出现数组越界的异常。

这个代码一次提交就Accept了。

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-Merge Sorted Array

题目： Given two sorted integer arrays A and B, merge B into A as one sorted array. Note:

我不是女神ヾ/ 2022年08月06日 13:03/ 0 赞/ 168 阅读

相关 Leetcode: Merge Sorted Array

题目： Given two sorted integer arrays A and B, merge B into A as one sorted array. Note

心已赠人/ 2022年08月05日 15:11/ 0 赞/ 3 阅读

相关 [leetcode-排序]--88. Merge Sorted Array

Question 88. Merge Sorted Array > Given two sorted integer arrays nums1 and nums2, merg

悠悠/ 2022年07月11日 23:27/ 0 赞/ 129 阅读

相关 [leetcode]: 88. Merge Sorted Array

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

水深无声/ 2022年06月15日 12:57/ 0 赞/ 158 阅读

相关 88. Merge Sorted Array

[88. Merge Sorted Array][] Given two sorted integer arrays nums1 and nums2, merge nums2

落日映苍穹つ/ 2022年06月08日 06:17/ 0 赞/ 143 阅读

相关 leetcode|88. Merge Sorted Array

问题描述： Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one so

素颜马尾好姑娘i/ 2022年05月26日 00:44/ 0 赞/ 45 阅读

相关 LeetCode 88.Merge Sorted Array (合并两个有序数组)

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

╰半橙微兮°/ 2022年05月10日 10:14/ 0 赞/ 183 阅读

相关（Java）leetcode-88 Merge Sorted Array

题目【合并两个有序数组】 Given two sorted integer arrays nums1 and nums2, merge nums2 into num

╰半夏微凉°/ 2022年02月25日 15:26/ 0 赞/ 177 阅读

相关【Leetcode】88. Merge Sorted Array

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

绝地灬酷狼/ 2022年02月22日 01:55/ 0 赞/ 178 阅读

相关【LeetCode】88. Merge Sorted Array

Introduction Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1

一时失言乱红尘/ 2022年02月15日 13:36/ 0 赞/ 430 阅读