加载中...

daily leetcode - merge-sorted-array - !

题目地址

https://leetcode.com/problems/merge-sorted-array/

题目描述

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

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n ) to hold additional elements from nums2.

Example:

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

Output: [1,2,2,3,5,6]

思路

混合插入有序数组,由于两个数组都是有序的,所有只要按顺序比较大小即可。题目中说了 nums1 数组有足够大的空间,说明不用 resize 数组,又给了 m 和 n,那就知道了混合之后的数组的大小,这样就从 nums1 和 nums2 数组的末尾开始一个一个比较,把较大的数,按顺序从后往前加入混合之后的数组末尾。需要三个变量 i,j,k,分别指向 nums1,nums2,和混合数组的末尾。进行 while 循环,如果 i 和 j 都大于 0,再看如果 nums1[i] > nums2[j],说明要先把 nums1[i] 加入混合数组的末尾,加入后 k 和 i 都要自减 1;反之就把 nums2[j] 加入混合数组的末尾,加入后 k 和 j 都要自减 1。循环结束后,有可能 i 或者 j 还大于等于 0,若 j 大于 0,那么还需要继续循环,将 nums2 中的数字继续拷入 nums1。若是 i 大于等于 0,那么就不用管,因为混合数组本身就放在 nums1 中,参见代码如下:

解法一:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<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--];
        }
        while (j >= 0) nums1[k--] = nums2[j--];
    }
};

我们还可以写的更简洁一些,将两个 while 循环融合到一起,只要加上 i>=0 且 nums1[i] > nums2[j] 的判断条件,就可以从 nums1 中取数,否则就一直从 nums2 中取数,参见代码如下:

解法二:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (j >= 0) {
            nums1[k--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
        }
    }
};

思路 2

符合直觉的做法是 将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 数组已经处理过的元素
  • 红色代表当前正在进行比较的元素
  • 绿色代表已经就位的元素

mark
mark
mark

关键点解析

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

代码

/*
 * @lc app=leetcode id=88 lang=javascript
 *
 * [88] Merge Sorted Array
 *
 * https://leetcode.com/problems/merge-sorted-array/description/
 *
 * algorithms
 * Easy (34.95%)
 * Total Accepted:    347.5K
 * Total Submissions: 984.7K
 * Testcase Example:  '[1,2,3,0,0,0]\n3\n[2,5,6]\n3'
 *
 * Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as
 * one sorted array.
 *
 * Note:
 *
 *
 * The number of elements initialized in nums1 and nums2 are m and n
 * respectively.
 * You may assume that nums1 has enough space (size that is greater or equal to
 * m + n) to hold additional elements from nums2.
 *
 *
 * Example:
 *
 *
 * Input:
 * nums1 = [1,2,3,0,0,0], m = 3
 * nums2 = [2,5,6],       n = 3
 *
 * Output: [1,2,2,3,5,6]
 *
 *
 */
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
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];
        }
    }
};

Python 代码

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/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode


标题: daily leetcode - merge-sorted-array - !
文章作者: lonuslan
文章链接: https://www.lonuslan.com/articles/2020/03/07/1583560979181.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LonusLan 👋🏼

评论