如何以最低复杂的插入缺少的日期？

Question

两个数组如下：

var date1 = ['2021/05/01','2021/05/02','2021/05/03','2021/05/04','2021/05/05',,'2021/05/06','2021/05/07'];
var date2 = ['2021/05/01','2021/05/03','2021/05/06','2021/05/07'];

怎样以较低的时间复杂度，在date2中对应位置(顺序排)插入，比date1缺少的日期？

Answer 1

假设输入并不是有序的时间复杂度O(NLog(N) + M Log(M)) 其中N为数组1的长度，M为数组2的长度，如果已经是有序的，可以删除排序的部分，时间复杂度可达到O(N)，N为两个数组长度的和

var date1 = [
  "2021/05/01",
  "2021/05/02",
  "2021/05/03",
  "2021/05/04",
  "2021/05/07",
  "2021/05/05",
  "2021/05/06",
  "2021/05/08"
];
var date2 = [
  "2021/05/01",
  "2021/05/03",
  "2021/05/09",
  "2021/05/06",
  "2021/05/07",
  "2021/05/20"
];

const strCompareFunc = (a, b) => {
  if (a < b) return -1;
  else if (a > b) return 1;
  else return 0;
};

const merge = (arr1, arr2) => {
  let index1 = 0;
  let index2 = 0;
  const ans = [];

  //如果两个数组已经是有序的了，可以省略掉这一步，时间复杂度会达到O(N)
  arr1.sort(strCompareFunc);
  arr2.sort(strCompareFunc);

  while (index1 < arr1.length || index2 < arr2.length) {
    let prev = ans[ans.length - 1] ?? null;
    if (index1 >= arr1.length) {
      if (arr2[index2] !== prev) {
        ans.push(arr2[index2]);
      }
      ++index2;
    } else if (index2 >= arr2.length) {
      if (arr1[index1] !== prev) {
        ans.push(arr1[index1]);
      }
      ++index1;
    } else {
      if (arr1[index1] < arr2[index2]) {
        if (arr1[index1] !== prev) ans.push(arr1[index1]);
        ++index1;
      } else if (arr1[index1] > arr2[index2]) {
        if (arr2[index2] !== prev) ans.push(arr2[index2]);
        ++index2;
      } else {
        if (arr1[index1] !== prev) ans.push(arr1[index1]);
        ++index1;
        ++index2;
      }
    }
  }

  return ans;
};

console.log(merge(date1, date2));

简单版本: 因为javascrit里面数组的sort函数默认就是按字典序排序的所以可以写成这样，时间复杂度O(N *Log(N))
相比前一版本对多出两轮迭代，而且使用了Set去重虽然理论上初始化Set的时间复杂度是O(N)但是还是要比上面那种一轮迭代直接去重的常数要大的

var date1 = [
  "2021/05/01",
  "2021/05/02",
  "2021/05/03",
  "2021/05/04",
  "2021/05/08",
  "2021/05/07",
  "2021/05/05",
  "2021/05/06"
];
var date2 = [
  "2021/05/01",
  "2021/05/09",
  "2021/05/03",
  "2021/05/06",
  "2021/05/07",
  "2021/05/20"
];

const merge = (arr1, arr2) => {
  return Array.from(new Set(arr1.concat(arr2)).values()).sort();
};

console.log(merge(date1, date2));

Answer 2

先对数据排序，然后确定谁的数据范围更大，最后比较相同位置的数据是否相同，不相同则把大范围集合中的数据插入到小范围集合对应的位置。

//假定排序和集合范围已确定
for(let i =0; i < date1.length; i ++) {
  if (date[i] && date1[i]!== date2[i]) {
    date2.splice(i, 0, date1[i]);
  }
}