JS算法题目4

Question

对比两个数组，input中比data中多了哪些元素？放入add。对比data中少了哪些元素？放入del

例：

let data = [5,6,8,10];
//输入：
let input = [5,8,10,15,18];

let add = []
let del = []
//输出：
add => [15,18] //因为input对比data多了15和18
del => [6] //因为input对比data少了6

Answer 1

好像以前回答过类似的问题，懒得去找了，也懒得写了，给你个思路

---

思路一

注意，这个思路是假设数组是集合的情况（即不考虑重复元素）

遍历 input，对每个元素去 data 中查找，找不到的就是多的。
返过来，遍历 data，每个元素去 input 中查找，找不到的就是少的。
这个方法最简单易行

Lodash 的 _.difference() 可以快速实现单向排除

import _ from "lodash";

const add = _.difference(input, data);
const del = _.difference(data, input);

自己简单实现 _.difference：

function difference(data, refs) {
    const set = new Set(refs);
    return data.filter(n => !set.has(n));
}

思路二

对 input 和 data 排序，用双指针（序号）遍历，挨个查找。
查找过程中，如果数组1在序号1位置的值1已经大于数组2在序号2位置的值2，还没有找到值2，那说明值2是数组2中有但数组1中没有的，此时调过来从 数组2[序号2+1] 开始跟 数组1[序号1] 比较直到数组2当前位置的值大于数组1当前位置的值……

这个写起来麻烦，不想写了。

---

在跟 @jsdeferred 讨论的过程中发现 @jsdeferred 的代码有点小问题，比如处理这样一个用例的时候：

let data = [5, 6, 8, 10, 5, 5, 5];
let input = [5, 8, 10, 15, 18, 8, 8, 8];

输出（我把结果改成对象了）

{
    add: [15, 18],
    del: [8, 8, 8, 5, 5, 5, 6]
}

下面是我根据 @jsdeferred 的思路写的代码：

const diff2 = (prev, cur) => {
    const map = new Map();

    prev.forEach(n => {
        map.set(n, (map.get(n) ?? 0) + 1);
    });

    cur.forEach(n => {
        map.set(n, (map.get(n) ?? 0) - 1);
    });

    const add = [];
    const del = [];
    Array.from(map)
        .forEach(([k, v]) => {
            if (v < 0) { add.push(...make(k, -v)); }
            if (v > 0) { del.push(...make(k, v)); }
        });

    function make(n, times) {
        const a = Array(times);
        a.fill(n);
        return a;
    }

    return { add, del };
};

// { add: [ 8, 8, 8, 15, 18 ], del: [ 5, 5, 5, 6 ] }

---

又研究了一下 make 可以写成一句话（纯为了好耍）

const make = (n, times) => ((a) => (a = Array(times).fill(n), a))();

Answer 2

const diff = (prev, cur) => {
  const map = {};

  for (let i = 0; i < prev.length; ++i) {
    if (typeof map[prev[i]] === "undefined") {
      map[prev[i]] = 0;
    }

    ++map[prev[i]];
  }

  const del = [];
  const add = [];

  for (let i = 0; i < cur.length; ++i) {
    if (typeof map[cur[i]] === "undefined") {
      add.push(cur[i]);
      continue;
    }

    if (--map[cur[i]] < 0) {
      add.push(cur[i]);
    }
  }

  for (const key of Object.keys(map)) {
    if (map[key] > 0) {
      del.push(...Array.from({ length: map[key] }, () => +key));
    }
  }

  return [del, add];
};

let data = [5, 6, 8, 10];
//输入：
let input = [5, 8, 10, 15, 18];

console.log(diff(data, input));

Answer 3

const data = [5,6,8,10];
//输入：
const input = [5,8,10,15,18];

const add = []
const del = []

// 先转成set
const dataSet = new Set(data)
// 增加的
for(let item of input){
  if(!dataSet.has(item)) del.push(item)
}

console.log(del);

// 先转成set
const inputSet = new Set(input)

// 增加的
for(let item of data){
  if(!inputSet.has(item)) add.push(item)
}

console.log(add);