图解leetcode88：合并两个有序数组

给你两个有序整数数组 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]

lleetcode

function twoNumConcat(num1, num2) {
  if (!(num1 instanceof Array)) {
    num1 = []
  }

  if (!(num2 instanceof Array)) {
    num2 = []
  }

  return num1.concat(num2).filter(item => item).sort((a, b) => a - b);
}

console.log(twoNumConcat([1, 2, 3, 0, 0, 0], [0, 2, 2, 4, 5]));

快慢指针走一波~

解题思路：

nums1 、 nums2 有序，若把 nums2 全部合并到 nums1 ，则合并后的 nums1 长度为 m+n
我们可以从下标 m+n-1 的位置填充 nums1 ，比较 nums1[len1] 与 nums2[len2] 的大小，将最大值写入 nums1[len]，即
- nums1[len1]>=nums2[len2] ，nums1[len--] = nums1[len1--] ,这里 -- 是因为写入成功后，下标自动建议，继续往前比较
- 否则 nums1[len--] = nums2[len2--]
边界条件：
- 若 len1 < 0 ，即 len2 >= 0 ，此时 nums1 已重写入， nums2 还未合并完，仅仅需要将 nums2 的剩余元素（0…len）写入 nums2 即可，写入后，合并完成
- 若 len2 < 0，此时 nums2 已全部合并到 nums1 ，合并完成

时间复杂度为 O(m+n)

代码实现：

const merge = function(nums1, m, nums2, n) {
    let len1 = m - 1,
        len2 = n - 1,
        len = m + n - 1
    while(len2 >= 0) {
        if(len1 < 0) {
            nums1[len--] = nums2[len2--]
            continue
        }
        nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--]: nums2[len2--]
    }
};

leetcode

function twoNumConcat(num1, num2) {
if (!(num1 instanceof Array)) {
num1 = []
}

if (!(num2 instanceof Array)) {
num2 = []
}

return num1.concat(num2).filter(item => item).sort((a, b) => a - b);
}

console.log(twoNumConcat([1, 2, 3, 0, 0, 0], [0, 2, 2, 4, 5]));

concat() 不会更改现有数组，会返回一个新数组

快慢指针走一波~

想法不错，不过不需要那么麻烦

var merge = function (nums1, m, nums2, n) {
nums1.splice(m,n,...nums2)
nums1.sort((a,b) => a-b)
return nums1
}

function mergeAry(left = [], right = []) {
  const result = [];
  while (left.length && right.length) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }
  return result.concat(left, right);
}

数组的toString方法，拿到数据，split，unique，sort
let arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]; let arrStr = arr.toString(); let result = Array.from(new Set(arrStr.split(',').map(item => parseInt(item)))).sort((a,b) => a-b); console.log(result)

nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--]: nums2[len2--]

时间复杂度感觉应该是O(n)吧

双指针法

/**
 * @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) {
  var p = nums1.length - 1, p1=m-1, p2=n-1
  while(p1 >=0 && p2 >=0){
    if(nums2[p2] > nums1[p1]){
      nums1[p]=nums2[p2]
      p2--;
      p--;
    }else{
      nums1[p]=nums1[p1]
      p1--
      p--
    }
  }
  while(p2>=0){// nums1指针没到头但是num2指针到头，不影响,nums2指针没到头要添加到nums1上
    nums1[p]=nums2[p2]
    p2--
    p--
  }
};

function twoNumConcat(num1, num2) {
  if (!(num1 instanceof Array)) {
    num1 = []
  }

  if (!(num2 instanceof Array)) {
    num2 = []
  }

  return num1.concat(num2).filter(item => item).sort((a, b) => a - b);
}

console.log(twoNumConcat([1, 2, 3, 0, 0, 0], [0, 2, 2, 4, 5]));

这也太暴力了吧。。

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
const merge = (nums1, m, nums2, n) => {
    let index1 = m - 1
    let index2 = n - 1
    let tail = m + n - 1
    while (index2 >= 0) {
        if (nums1[index1] > nums2[index2]) {
            nums1[tail] = nums1[index1]
            index1--
            tail--
        } else {
            nums1[tail] = nums2[index2]
            index2--
            tail--
        }
    }
}

let nums1 = [1, 2, 3];
let nums2 = [2, 5, 6];
merge(nums1, 3, nums2, 3)
console.log(nums1)

function merge (num1, num2, m, n) {
num2.splice(n, num2.length - n)
num1.splice(m, num1.length - m, ...num2)
num1.sort((a, b) => { return a - b })
return num1
}

题目地址（88. 合并两个有序数组）

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

题目描述

给定两个有序整数数组 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

前置知识

归并排序

思路

符合直觉的做法是将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 过程。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;
}

但是 merge sort 很多时候，合并的时候我们通常是新建一个数组，但是这道题目要求的是原地修改.这就和 merge sort 的 merge 过程有点不同。这里要求原地修改。如果使用类似上面的方法，如果采用从头开始遍历，需要将 nums1 的前 m 个数组放到另一个数组中避免写指针写入的干扰。这样空间复杂度就是 $O(m)$。其实我们能只要从后往前比较，并从后往前插入即可。

我们需要三个指针：

写指针 current，用于记录当前填补到那个位置了
m 用于记录 nums1 数组处理到哪个元素了
n 用于记录 nums2 数组处理到哪个元素了

如图所示：

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

关键点解析

从后往前比较，并从后往前插入，这样可避免写指针影响，同时将空间复杂度降低到 $O(1)$

代码

代码支持：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.
        """
        pos = m + n - 1
        while m > 0 and n > 0:
            if nums1[m - 1] < nums2[n - 1]:
                nums1[pos] = nums2[n - 1]
                n -= 1
            else:
                nums1[pos] = nums1[m - 1]
                m -= 1
            pos -= 1
        while n > 0:
            nums1[pos] = nums2[n - 1]
            n -= 1
            pos -= 1

复杂度分析

时间复杂度：$O(M + N)$
空间复杂度：$O(1)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。目前已经 40K star 啦。

大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

var merge = function (nums1, m, nums2, n) {
  var i1 = m - 1;
  var i2 = n - 1;
  var index = m + n - 1;

  while (i2 >= 0) {
    var currIsNums1 = i1 >= 0 ? (nums1[i1] - nums2[i2] > 0) : false;
    nums1[index--] = currIsNums1 ? nums1[i1--] : nums2[i2--];
  }
};

var merge = function (nums1, m, nums2, n) {
  var i1 = m - 1;
  var i2 = n - 1;
  var index = m + n - 1;

  while (i2 >= 0) {
    var currIsNums1 = i1 >= 0 ? (nums1[i1] - nums2[i2] > 0) : false;
    nums1[index--] = currIsNums1 ? nums1[i1--] : nums2[i2--];
  }
};

var merge = function(nums1, m, nums2, n) {
    nums1.splice(m,n,...nums2);
    nums1.sort((a,b)=>{
        return a-b;
    });
    return nums1;
};

var merge = function(nums1,m,mums2,n){
nums1.splice(m,nums.length-m,...nums2);
nums1.sort((a,b)=>a-b}
return nums1
}

合并排序

function merge(nums1, m, nums2, n) {
  let current = m + n;
  while (m + n > 0) {
    if (m == 0) {
      nums1[--current] = nums2[--n];
      continue;
    }
    if (n == 0) {
      nums2[--current] = nums1[--m];
      continue;
    }
    nums1[--current] = nums1[m - 1] > nums2[n - 1] ? nums1[--m] : nums2[--n];
  }
}

var merge = function(nums1, m, nums2, n) {
nums1.length = m;
for(let i = 0; i < n; i++){
nums1[m++] = nums2[i]
}
nums1.sort((a,b)=>{return a-b})
return nums1
};

leetcode
let nums1 = [2, 3, 7]
let nums2 = [1, 2, 9]

function solve1(num = [], m, mun2 = [], n) {
    //不考虑性能,较为简洁的实现,时间复杂度高
    return num1.splice(0, m).concat(num2.splice(0, n)).sort((a, b) => a - b)
}
function solve2(num = [], m, num2 = [], n) {
    //单次for循环,(O(n+m))
    let len1 = m - 1, len2 = n - 1;
    for (let index = n + m - 1; index > 0; index--) {
        if (len1 < 0) {
            num1[index] = num2[len2--]
        }
        else if (len2 < 0) {
            num1[index] = num1[len1--]
        }
        else num1[index] = num1[len1] > num2[len2] ? num1[len1--] : num2[len2--]
    }
    return num
}
function solve3(num = [], m, num2 = [], n) {
    //利用while循环判断,(O(n+m))
    let len1 = m - 1, len2 = n - 1, len = n + m - 1;
    while (len1 >= 0) {
        if (len2 < 0) {
            num[len--]=len1--
        }
        else num[len--] = num1[len1] > num2[len2] ? num1[len1--] : num2[len2--]
    }
    return  num
}
// console.log(solve1(num1, m, num2, n));

LeetCode链接：https://leetcode-cn.com/problems/merge-sorted-array/

难度：简单

解法一：合并数组，然后排序

/*
 * @lc app=leetcode.cn id=88 lang=javascript
 *
 * [88] 合并两个有序数组
 */

// @lc code=start
/**
 * @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.splice(m, n, ...nums2)
  
  nums1.sort((a, b) => a - b)
};
// @lc code=end

分析

利用split方法，拼接两个数组，然后进行排序。

解法二：从后往前插入

/*
 * @lc app=leetcode.cn id=88 lang=javascript
 *
 * [88] 合并两个有序数组
 */

// @lc code=start
/**
 * @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) {
  // 指向插入的尾部
  let tail = m + n
  // 指向 nums1 的尾部(不包括空位)
  let nums1Tail = m - 1
  // 指向 nums2 的尾部
  let nums2Tail = n - 1

  while (tail--) {
    // 检查: 指针下标不合法, 直接退出循环
    if(nums1Tail === -1 || nums2Tail === -1) break

    // 通过比较得出这次循环应该存储的值
    const res =
      nums1[nums1Tail] > nums2[nums2Tail]
        ? nums1[nums1Tail--]
        : nums2[nums2Tail--]

    nums1[tail] = res
  }

  // 边界处理: 存在 nums2 中的值还没有被完全遍历的情况
  while(nums2Tail !== -1) {
    nums1[tail--] = nums2[nums2Tail--]
  }
  
}
// @lc code=end

分析

设置三个指针

nums1Tail 指向 nums1 的末尾（不包括空位）
nums2Tail 指向 nums2 的末尾
Tail 指向 nums1 真正的末尾（包括空位）

然后，对 nums1Tail 和 nums2Tail 所指向的值进行比较，将较大的放置在 tail 指针指向的位置。

接着，更新指针指向位置。直到指针出现非法值，跳出循环。

最后，可能存在 nums2 数组中的值还没有完全遍历，就因为指针出现非法值而停止。因此，我们最后做一个边界处理，将 nums2 中的剩下的值直接插入到 tail 对应的位置。

为什么能直接插入？因为 nums2 中未遍历到的值，肯定都是比 nums1 当前要小的，不然早就放出去了。

边界情况的例子：

[4,5,6,0,0,0]
3
[1,2,3]
3

let a1 = [1,2,3,0,0,0];
let a2 = [2,5,6];
a1.splice(a2.length,a2.length,...a2)
a1.sort((a,b)=>(a-b))

function merge(arr1, arr2) {
  let len1 = arr1.length;
  let len2 = arr2.length;
  let i = 0;
  let j = 0;
  while (i < len1 && j < len2) {
    if (arr1[i] > arr2[j]) {
      arr1.splice(i, 0, arr2[j]);
      i++;
      j++;
    } else {
      i++;
    }
  }
  return arr1;
}

function foo(ar1, ar2) {
if ((ar1 instanceof Array && ar1.length !== 0) || (ar2 instanceof Array && ar2.length)) {
let i = 0;
while (i < ar2.length) {
ar1.push(ar2[i])
i++;
}
}
ar1.sort((a, b) => a - b)
}

Navigation Menu

Repository navigation

图解leetcode88：合并两个有序数组 #3

15 remaining items

题目地址（88. 合并两个有序数组）

题目描述

公司

前置知识

思路

关键点解析

代码

解法一：合并数组，然后排序

分析

解法二：从后往前插入

分析

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

图解leetcode88：合并两个有序数组 #3

Description

Activity

BoswellJi commented on Apr 3, 2020

chenzesam commented on Apr 3, 2020

sisterAn commented on Apr 3, 2020

sisterAn commented on Apr 3, 2020

sisterAn commented on Apr 3, 2020

fishTwelve commented on Apr 6, 2020

Loading-m commented on Apr 7, 2020

ChaoshengZhang commented on Apr 8, 2020

whitesky1225 commented on Apr 19, 2020

Aiyoweioo commented on Apr 26, 2020

plane-hjh commented on Apr 28, 2020

15 remaining items

AnranS commented on Nov 16, 2020

smileCris commented on Jan 25, 2021

azl397985856 commented on Mar 3, 2021

题目地址（88. 合并两个有序数组）

题目描述

公司

前置知识

思路

关键点解析

代码

ReAlign commented on Jul 26, 2021

ReAlign commented on Jul 26, 2021

jack-hate-titanic commented on Jul 31, 2021

Deadpool957 commented on Aug 16, 2021

CrazyPeter commented on Sep 27, 2021

painting-alt commented on Oct 6, 2021

nunuji123 commented on Oct 18, 2021

sionnigjt commented on Oct 22, 2021

fa3eng commented on Jan 10, 2022

解法一：合并数组，然后排序

分析

解法二：从后往前插入

分析

hedengxing commented on Sep 8, 2022

fengjinlong commented on Dec 17, 2022

jf179 commented on Jan 9, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions