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

这也太暴力了吧。。