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

[sisterAn]

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

[BoswellJi]

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]));

[chenzesam]

快慢指针走一波~

[sisterAn]

解题思路：

• 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

[sisterAn]

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() 不会更改现有数组，会返回一个新数组

[sisterAn]

快慢指针走一波~

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

[fishTwelve]

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

[Loading-m]

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);
}

[ChaoshengZhang]

数组的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)

[whitesky1225]

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

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

[Aiyoweioo]

双指针法

/**
 * @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--
  }
};

[plane-hjh]

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]));

这也太暴力了吧。。

[Sakura-pgh]

function mergeArr(num1, num2, m, n) {
  for (let i = m + n - 1; i > 0; i--) {
    num1[i] = num1[m - 1] >= num2[n - 1] ? num1[m - 1] : num2[n - 1];
    num1[m - 1] >= num2[n - 1] ? m-- : n--;
  }
  console.log(num1);
  return num1;
}

[babybrotherzb]

var merge = function(nums1, m, nums2, n) {
 let length = m+n
for(let i = length-1;(i>=0&&n>0);i--){
if(m!=0&&nums1[m-1]>nums2[n-1]){
    nums1[i]=nums1[m-1]
    m--
}else{
    nums1[i]=nums2[n-1]
    n--
}
}
};

[guanping1210]

题目要求： 1、是在第一个数组上直接操作修改，不开辟新得内存空间 2、小于0的数据，会被干掉

     const towNumConcat = (arr1, arr2) => {
            arr1.splice(arr1.length - 1, 0, ...arr2).sort() // 将arr2添加到arr1上
            if(arr1[0] <= 0) {
                arr1.splice(0, arr1.lastIndexOf(arr1[0]) + 1)
            }
        }

[whace]

三行代码 内存击败100% var merge = function(nums1, m, nums2, n) { for(let i = 0; i< n; i++){ nums1[i+m] = nums2[i] } nums1.sort((a,b)=>a -b) };

[iconWave]

const twoNumConcat = (arr1, arr2) => {
  arr1.splice(arr1.length - 1, 0, ...arr2)
  arr1.sort((a, b) => a - b)
  for(let i = 0; i < arr1.length; i++) {
    if (arr1[i] === 0) {
      arr1.splice(i, 1)
      i--
    }
  }
  return arr1
}

[7777sea]

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

[FE-wuhao]

 while(len2 >= 0) {
        if(len1 < 0) {
            nums1[len--] = nums2[len2--]
            continue
        }
        nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--]: nums2[len2--]
    }

小姐姐，此处为什么是continue写法,如果我直接后面用else的话性能上有什么差距吗？

 while(len2 >= 0) {
        if(len1 < 0) nums1[len--] = nums2[len2--]
        else nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--]: nums2[len2--]
    }

[Been101]

let num2 = [1, 2, 3, 4, 5]
let num1 = [2, 7, 8, 10]
let len1 = num1.length - 1
let len2 = num2.length - 1
let len =  num1.length+ num2.length - 1
function mergeArray(num1, num2, len1, len2, len) {
  while (len1 >= 0 && len2 >= 0) {
    num1[len--] = num1[len1] <= num2[len2] ? num2[len2--] : num1[len1--]
  }

  if (len1 >= 0) return num1 // len1 有值， 说明num2 已经全部merge 到 num1

  // len2 有值， 说明num1 已经到头了
  // 且num1[0] 的值比 num2剩下的最大的值还大， 所以把 num2 剩下的值放在num1的最前面就可以了
  if (len2 >= 0) {
    while (len2 > -1) {
      num1[len--] = num2[len2--]
    }
  }
  return num1
}

[xyyVee]

边界条件： 若 len1 < 0 ，即 len2 >= 0 ，此时 nums1 已重写入， nums2 还未合并完，仅仅需要将 nums2 的剩余元素（0…len）写入 nums2 即可，写入后，合并完成

仅仅需要将 nums2 的剩余元素（0…len）写入 nums2

应该是将 nums2 的剩余元素（0…len）写入 nums1把？

[Verahuan]

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]));

数组方法的复杂度可高了

[fivge]

JavaScript 双指针纯函数

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
let merge = function (nums1, m, nums2, n) {
  //   nums1[m + n - 1];
  // 定义两个指针指向两个数组最后一位
  let i = m - 1;
  let j = n - 1;

  for (; i >= -1 && j >= 0; ) {
    if (nums1[i] <= nums2[j]) {
      nums1[i + j + 1] = nums2[j];
      j--;
      continue;
    }

    if (nums1[i] > nums2[j]) {
      nums1[i + j + 1] = nums1[i];
      i--;
      continue;
    }

    if (i === -1) {
      nums1[i + j + 1] = nums2[j];
      j--;
      continue;
    }
  }
};

[nocodeempire]

楼上几个concat返回的是新数组, 不符题意;

const pushSort = (num1, num2) => {
num1.push(...num2);
return num1.sort((a, b) => a -b);
}
let a = [1,2,3,4]; 
let b = [2,3,23,4];
pushSort(a,b);  // [1, 2, 2, 3, 3, 4, 4, 23]
a  // [1, 2, 2, 3, 3, 4, 4, 23]

[AnranS]

/**
 * @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)

[smileCris]

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 }

[azl397985856]

题目地址（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)$。其实我们能只要从后往前比较，并从后往前插入即可。

我们需要三个指针：

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

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

3. 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 啦。

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

[ReAlign]

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--];
  }
};

[ReAlign]

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--];
  }
};

[jack-hate-titanic]

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

[Deadpool957]

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