1. 首页

LeetCode 088. 合并两个有序数组

题目描述

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:

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

输出: [1,2,2,3,5,6]

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • loomberg
  • facebook
  • microsoft

难度:Middle

前置知识

  • 归并排序

思路

符合直觉的做法是将nums2插到num1的末尾, 然后排序

具体代码:

// 这种解法连m都用不到
// 这显然不是出题人的意思
if (n === 0) return;
let current2 = 0;
for (let i = nums1.length - 1; i >= nums1.length - n; i--) {
  nums1[i] = nums2[current2++];
}
nums1.sort((a, b) => a - b); // 当然你可以自己写排序,这里懒得写了,因为已经偏离了题目本身

这道题目其实和基本排序算法中的merge sort非常像,但是 merge sort 很多时候,合并的时候我们通常是
新建一个数组,这样就很简单。 但是这道题目要求的是原地修改.

这就和 merge sort 的 merge 过程有点不同,我们先来回顾一下 merge sort 的 merge 过程。

merge 的过程可以是先比较两个数组的头元素,然后将较小的推到最终的数组中,并将其从原数组中出队列。
循环直到两个数组都为空。

具体代码如下:

// 将nums1 和 nums2 合并
function merge(nums1, nums2) {
  let ret = [];
  while (nums1.length || nums2.length) {
    // 为了方便大家理解,这里代码有点赘余
    if (nums1.length === 0) {
      ret.push(nums2.shift());
      continue;
    }

    if (nums2.length === 0) {
      ret.push(nums1.shift());
      continue;
    }
    const a = nums1[0];
    const b = nums2[0];
    if (a > b) {
      ret.push(nums2.shift());
    } else {
      ret.push(nums1.shift());
    }
  }
  return ret;
}

这里要求原地修改,其实我们能只要从后往前比较,并从后往前插入即可。

我们需要三个指针:

  1. current 用于记录当前填补到那个位置了

  2. m 用于记录 nums1 数组处理到哪个元素了

  3. n 用于记录 nums2 数组处理到哪个元素了

如图所示:

  • 灰色代表 num2 数组已经处理过的元素
  • 红色代表当前正在进行比较的元素
  • 绿色代表已经就位的元素

88.merge-sorted-array-1
88.merge-sorted-array-2
88.merge-sorted-array-3

关键点解析

  • 从后往前比较,并从后往前插入

代码

代码支持:Python3, C++, Java, JavaScript

JavaSCript Code:

var merge = function (nums1, m, nums2, n) {
  // 设置一个指针,指针初始化指向nums1的末尾(根据#62,应该是index为 m+n-1 的位置,因为nums1的长度有可能更长)
  // 然后不断左移指针更新元素
  let current = m + n - 1;

  while (current >= 0) {
    // 没必要继续了
    if (n === 0) return;

    // 为了方便大家理解,这里代码有点赘余
    if (m < 1) {
      nums1[current--] = nums2[--n];
      continue;
    }

    if (n < 1) {
      nums1[current--] = nums1[--m];
      continue;
    }
    // 取大的填充 nums1的末尾
    // 然后更新 m 或者 n
    if (nums1[m - 1] > nums2[n - 1]) {
      nums1[current--] = nums1[--m];
    } else {
      nums1[current--] = nums2[--n];
    }
  }
};

C++ code:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int current = m + n - 1;
        while (current >= 0) {
            if (n == 0) return;
            if (m < 1) {
                nums1[current--] = nums2[--n];
                continue;
            }
            if (n < 1) {
                nums1[current--] = nums1[--m];
                continue;
            }
            if (nums1[m - 1] > nums2[n - 1]) nums1[current--] = nums1[--m];
            else nums1[current--] = nums2[--n];
        }
    }
};

Java Code:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1, j=n-1, k=m+n-1;
        // 合并
        while(i>=0 && j>=0)
        {
            if(nums1[i] > nums2[j])
            {
                nums1[k--] = nums1[i--];
            }
            else
            {
                nums1[k--] = nums2[j--];
            }
        }
        // 合并剩余的nums2
        while(j>=0)
        {
            nums1[k--] = nums2[j--];
        }
    }
}

Python Code:

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # 整体思路相似,只不过没有使用 current 指针记录当前填补位置
        while m > 0 and n > 0:
            if nums1[m-1] <= nums2[n-1]:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
            else:
                nums1[m+n-1] = nums1[m-1]
                m -=1
        """
        由于没有使用 current,第一步比较结束后有两种情况:
            1. 指针 m>0,n=0,此时不需要做任何处理
            2. 指针 n>0,m=0,此时需要将 nums2 指针左侧元素全部拷贝到 nums1 的前 n 位
        """
        if n > 0:
            nums1[:n] = nums2[:n]

复杂度分析

更多题解可以访问我的 前端中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 088. 合并两个有序数组

链接:https://www.javascriptc.com/4448.html

« 前端音视频之WebRTC初探
LeetCode 087. 扰乱字符串»
Flutter 中文教程资源

相关推荐

QR code