合并两个有序数组( LeetCode 88 )

本文内容为算法训练营一期内容,仅限训练营学员观看

一、题目描述

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

初始化 nums1nums2 的元素数量分别为 m 和 n 。

你可以假设 nums1 的空间大小等于 m + n,这样它就有足够的空间保存来自 nums2 的元素。

二、题目解析

设置两个索引 ij 分别指向 nums1 和 nums2 的有效元素的尾部,从它们的尾部开始向前遍历,同时设置索引 cur 指向 nums1最末尾,在每次遍历过程中,比较 ij 指向的元素值大小,把大的元素填充到 cur 的位置,填充完毕说明那个元素已经放置在它应该放置的位置,不需要在管它了,把 cur 向前移动,同时把 i 或者 j 向前移动,继续比较 ij 指向的元素值大小,把大的元素填充到 cur 的位置。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com/555.html
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并两个有序数组( LeetCode 88 ):https://leetcode-cn.com/problems/merge-sorted-array/
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 索引从有序数组 nums1 有效元素的末端开始
        // 数组的下标索引从零开始计数
        // 索引   0    1     2
        // 数组 [ 1 ,  2  ,  3 ]
        int i = m - 1;

        // 索引从有序数组 nums2 的末端开始
        int j = n - 1;

        // 从有序数组 nums1 最末端的位置开始保存元素
        int cur = nums1.length - 1;

        // 通过循环把 num2 的元素都移动到 num1 中
        while( j >= 0  ){

            // 比较 num1 和 num2 中当前的元素大小

            // 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
            // 为了防止越界 i 必须是大于等于 0 
            if( i >=0 && nums1[i] > nums2[j] ){

             // 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
             // 此时 cur 的元素已经确定下来
             nums1[cur] = nums1[i];

             // 接下来去确定 cur 前面一个元素应该放什么数字
             cur--;
             // 此时,索引 i 需要向前移动
             i--;
             // 否则,如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
            }else{

             // 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
             nums1[cur] = nums2[j];
             // 接下来去确定 cur 前面一个元素应该放什么数字
             cur--;
             // 此时,索引 j 需要向前移动
             j--;
            }
        }
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com/555.html
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并两个有序数组( LeetCode 88 ):https://leetcode-cn.com/problems/merge-sorted-array/
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // 索引从有序数组 nums1 有效元素的末端开始
        // 数组的下标索引从零开始计数
        // 索引   0    1     2
        // 数组 [ 1 ,  2  ,  3 ]
        int i = m - 1;

        // 索引从有序数组 nums2 的末端开始
        int j = n - 1;

        // 从有序数组 nums1 最末端的位置开始保存元素
        int cur = nums1.size() - 1;

        // 通过循环把 num2 的元素都移动到 num1 中
        while( j >= 0  ){

            // 比较 num1 和 num2 中当前的元素大小

            // 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
            // 为了防止越界 i 必须是大于等于 0 
            if( i >=0 && nums1[i] > nums2[j] ){

             // 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
             // 此时 cur 的元素已经确定下来
             nums1[cur] = nums1[i];

             // 接下来去确定 cur 前面一个元素应该放什么数字
             cur--;
             // 此时,索引 i 需要向前移动
             i--;
             // 否则,如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
            }else{

             // 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
             nums1[cur] = nums2[j];
             // 接下来去确定 cur 前面一个元素应该放什么数字
             cur--;
             // 此时,索引 j 需要向前移动
             j--;
            }
        }
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https:#www.algomooc.com/555.html
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 合并两个有序数组( LeetCode 88 ):https:#leetcode-cn.com/problems/merge-sorted-array/
class Solution :
   def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 索引从有序数组 nums1 有效元素的末端开始
        # 数组的下标索引从零开始计数
        # 索引   0    1     2
        # 数组 [ 1 ,  2  ,  3 ]
        i = m - 1

        # 索引从有序数组 nums2 的末端开始
        j = n - 1

        # 从有序数组 nums1 最末端的位置开始保存元素
        cur = m + n - 1

        # 通过循环把 num2 的元素都移动到 num1 中
        while j >= 0  :

            # 比较 num1 和 num2 中当前的元素大小

            # 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
            # 为了防止越界 i 必须是大于等于 0 
            if  i >=0 and nums1[i] > nums2[j]:

             # 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
             # 此时 cur 的元素已经确定下来
             nums1[cur] = nums1[i]

             # 接下来去确定 cur 前面一个元素应该放什么数字
             cur-=1
             # 此时,索引 i 需要向前移动
             i-=1
             # 否则,如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
            else:

             # 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
             nums1[cur] = nums2[j]
             # 接下来去确定 cur 前面一个元素应该放什么数字
             cur-=1
             # 此时,索引 j 需要向前移动
             j-=1

四、动画理解(没有声音)

隐藏内容
  • 普通用户购买价格:不可购买
  • 会员用户购买价格:999积分
  • 永久会员用户购买价格:免费推荐

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(6)

  • C⃰us⃰ter ༽ 永久会员 2021年7月31日 下午1:14

    impl Solution {
        pub fn merge(nums1: &mut Vec, m: i32, nums2: &mut Vec, n: i32) {
            // 索引从有序数组 nums1 有效元素的末端开始
            // 数组的下标索引从零开始计数
            // 索引  0  1  2
            // 数组 [1, 2, 3]
            let mut i = m – 1;
            // 索引从有序数组 nums2 的末端开始
            let mut j = n – 1;
            // 从有序数组 nums1 最末端的位置开始保存元素
            let mut cur = m + n – 1;

            // 通过循环把 nums2 的元素都移动到 nums1 中
            while j >= 0 {
                // 比较 nums1 和 nums2 中当前的元素大小
                // 如果 nums1 中的索引位置为 i 的元素大于 nums2 中索引位置为 j 的元素
                // 为了防止越界 i 必须大于等于 0
                if i >= 0 && nums1[i as usize] > nums2[j as usize] {
                    // 把 nums1 中的索引位置为 i 的元素复制到索引为 cur 的位置
                    // 此时 cur 的元素已经确定下来
                    nums1[cur as usize] = nums1[i as usize];
                    // 接下来去确定 cur 前面一个元素应该放什么数字
                    cur -= 1;
                    // 此时,索引 i 需要向前移动
                    i -= 1;
                    // 否则,如果 nums1 中的索引位置为 i 的元素小于或等于 nums2 中索引位置为 j 的元素
                } else {
                    // 把 nums2 中的索引位置为 j 的元素复制到索引为 cur 的位置
                    nums1[cur as usize] = nums2[j as usize];
                    // 接下来去确定 cur 前面一个元素应该放什么数字
                    cur -= 1;
                    // 此时,索引 j 需要向前移动
                    j -= 1;
                }
            }
        }
    }

  • 西西里里 永久会员 2021年10月9日 下午7:54

    重新上传带注释的C++版本
    class Solution {
    public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
    //设置两个标记指向nums1和num2有效值末端
    int i = m-1;
    int j = n-1;
    //在数组nums1整个长度的末尾设置一个标记点
    int cur = nums1.size()-1;

    //当标记 j 的索引不小于0时,执行下面的循环
    while(j>=0){
    //判断标记 i 的索引值是否小于零 以及 nums1有效值尾部 和 nums2有效值尾部的值的大小关系
    if(i>=0 && nums1[i]>nums2[j])
    {
    //给数组 nums1 对应的位置赋值
    nums1[cur] = nums1[i];

    cur–; //标记左移

    i–; //标记左移
    }
    else{
    //给 nums1 对应的位置赋值
    nums1[cur] = nums2[j];
    cur–; //标记左移
    j–; //标记左移
    }
    }
    }
    };

  • Lazy宇 永久会员 2021年10月13日 下午4:08

    JS解法
    “`js
    var merge = function(nums1, m, nums2, n) {
    let pointer = m + n – 1
    m —
    n —
    while(n >= 0) {
    if(nums1[m] > nums2[n]) {
    nums1[pointer –] = nums1[m –]
    } else {
    nums1[pointer –] = nums2[n –]
    }
    }
    return nums1
    };
    “`