JS算法题目4

Lambo
  • 313

对比两个数组,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
回复
阅读 677
3 个回答
✓ 已被采纳

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


思路一

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

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

思路二

inputdata 排序,用双指针(序号)遍历,挨个查找。
查找过程中,如果数组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))();
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));

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);
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏