跳到主要内容

并集

2023年06月19日
柏拉文
越努力，越幸运

一、合并无序数组​

有两数组 array1 和 array2, 实现一个 union 函数，使得合并 array1 和 array2 组成一个新的数组。

1.1 Lodash​

1.2 Bolawen Set​

function union(array1,array2){
    return Array.from(new Set([...array1, ...array2]));
}

1.3 Bolawen filter includes​

function union(array1,array2){
    return [...array1, ...array2.filter(item => !array1.includes(item))];
}

二、合并有序数组​

有两个有序数组 array1 和 array2, 实现一个 union 函数，使得合并 array1 和 array2 组成一个新的有序数组。

2.1 新数组双指针​

function union(array1, array2) {
  let i = 0;
  let j = 0;
  const result = [];

  while (i < array1.length && j < array2.length) {
    if (i >= array1.length) {
      result.push(array2[j++]);
    } else if (j >= array2.length) {
      result.push(array1[i++]);
    } else if (array1[i] > array2[j]) {
      result.push(array2[j++]);
    } else if (array1[i] < array2[j]) {
      result.push(array1[i++]);
    } else {
      result.push(array1[i++]);
      j++;
    }
  }

  return result;
}

2.2 原地数组逆向双指针​

思路: 可以指针设置为从后向前遍历，每次取两者之中的较大者放进 nums1 的最后面

实现

function union(array1, array2) {
  let curr;
  let i = array1.length - 1;
  let j = array2.length - 1;
  let tail = array1.length + array2.length - 1;

  while (i >= 0 && j >= 0) {
    if (i === -1) {
      curr = array2[j--];
    } else if (j === -1) {
      curr = array1[i--];
    } else if (array1[i] > array2[j]) {
      curr = array1[i--];
    } else {
      curr = array2[j--];
    }
    array1[tail--] = curr;
  }
}