算法----合并两个有序数组

算法----合并两个有序数组

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

初始化 nums1nums2 的元素数量分别为 mn 。你可以假设 nums1 的空间大小等于 m + n,这样它就有足够的空间保存来自 nums2 的元素。

例 1:

输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]

示例 2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]

提示:

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[i] <= 109

运行代码:

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

分析:

  1. 因为nums1只有前面m个参数有序的,后面的0为无效参数,所以可以从后往前插入,这样就可以直接在原来的数组上进行操作,不用消耗其他的空间资源;
  2. 其后续遍历nums1的开始位置是n+m-1;因为其数组是从0开始的,也可以从nums1.length-1开始,因为nums1.length==m+n
  3. 然后通过while循环开始遍历,当num2的数值都移动到num1上时,跳出循环。因为在循环中,如果nums2的元素都比nums1最后一个大的话,直接移动到nums1后面即完成排序。如果存在nums1nums2的元素大的话,也是nums1的元素在原数组中进行位置移动,其也是以nums都移动到nums1数组为终止条件。(有点像插入排序的思想)

参考:https://leetcode-cn.com/problems/merge-sorted-array/

上一篇:python实现两个数组的交集II


下一篇:力扣算法:两个数组的交集