V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
waiaan
V2EX  ›  JavaScript

请教两个数组对比的问题

  •  
  •   waiaan · 143 天前 · 2966 次点击
    这是一个创建于 143 天前的主题,其中的信息可能已经有所发展或是发生改变。
    const arr1=[a,b,c,d,e,f]
    const arr2=[d,b,c,a,g,h]
    

    需求是:arr2 中的元素如果不在 arr1 中就删除,arr1 中的元素如果不在 arr2 中就要 push 进 arr2 ( arr2 中元素的前后顺序不能变)。 目前想到的就是各遍历一次 arr1 和 arr2 ,有什么更好的方法吗? 谢谢。

    第 1 条附言  ·  143 天前
    数组中的元素都是对象,不是基本类型的数据。
    arr2 中的元素排列顺序不能变。
    目前做法是两次双层循环:先遍历 arr2 的每个元素,再循环 arr1 看有没有这个元素,没有就删除;接着遍历 arr1 的每个元素,再循环 arr2 看有没有这个元素,没有就从数组末尾添加。
    第 2 条附言  ·  143 天前
    采用了 13 楼的代码,谢谢。
    20 条回复    2024-06-19 16:44:26 +08:00
    FishBear
        1
    FishBear  
       143 天前   ❤️ 1
    paopjian
        2
    paopjian  
       143 天前
    好奇怪的需求啊,执行完 arr2 不在 arr1 的删除,就是[a,b,c,d],是取交集,那第二步 arr1 元素加入到 arr2,arr2 不就和 arr1 相同了?

    如果是分开的话:
    arr2.filter((x)=>arr1.includes(x))
    arr2.concat(arr1.filter(x=>!arr2.includes(x)))
    renmu
        3
    renmu  
       143 天前 via Android
    遍历做哈希,然后遍历比较,时间复杂度是 O(n)
    NessajCN
        4
    NessajCN  
       143 天前
    那结果不就是 arr1 吗....还是说 arr1 和 arr2 里有重复元素,所以结果是 arr1 先去重然后加入 arr2 里的重复元素?
    jorneyr
        5
    jorneyr  
       143 天前
    使用 HashSet 的快速查找功能,利用空间换时间,效率为 O(n)。
    创建 arr1Set
    创建 arr2Set
    然后再分别遍历 arr2 和 arr1 进行处理。
    waiaan
        6
    waiaan  
    OP
       143 天前
    @NessajCN
    @paopjian

    确实结果是 arr1 ,但是不能用 arr1 去替换 arr2 ,因为 arr2 中的元素是对象,同样是 a 元素,唯一标识相同、字段名相同,但是字段的值在 arr2 中有修改过。
    InDom
        7
    InDom  
       143 天前
    let arr3 = Array.from(new Set(arr2.filter(x => (new Set(arr1)).has(x)).concat(arr1)))
    waiaan
        8
    waiaan  
    OP
       143 天前
    @NessajCN
    @paopjian

    而且顺序也不一样。
    iOCZS
        9
    iOCZS  
       143 天前
    老老实实写没错的
    Sawyerhou
        10
    Sawyerhou  
       143 天前
    用带顺序的集合试试?顺序控制自建一个比较函数,或者加个序号,然后直接求差集、交集。
    EchoWhale
        11
    EchoWhale  
       143 天前
    已经是 O(n)了, 真的还能有更好的吗?
    chihiro2014
        12
    chihiro2014  
       143 天前
    这和我做的一个表格表头同步的需求很像
    oamu
        13
    oamu  
       143 天前   ❤️ 1
    ``` JavaScript
    // 返回用 arr2 中的对象更新 arr1 后的数组,数组按 arr2 中相对顺序排序
    function merge(arr1, arr2) {
    const map = new Map();
    const ans = [];
    arr1.forEach((obj) => map.set(obj.id, obj));
    arr2.forEach((obj) => {
    if (map.has(obj.id)) {
    ans.push(obj);
    map.delete(obj.id);
    }
    });
    return ans.concat(Array.from(map.values()));
    }
    ```
    ZztGqk
        14
    ZztGqk  
       143 天前 via iPhone
    整两个 set 做交并补吧
    chendl111
        15
    chendl111  
       143 天前
    需求目的就是把 arr1 的元素复制到 arr2 并且删除 arr1 没有的元素。
    那么对两个数组分别 set ,找出差集,双指针扫一遍,复杂度 Onlogn
    Marthemis
        16
    Marthemis  
       143 天前
    感觉优化的空间不是很大。

    ```js
    const map1 = new Map()
    const map2 = new Map()
    arr1.forEach(e => {
    map1.set(e.key, e)
    });
    arr2.forEach(e => {
    if (map1.has(e.key)) {
    map2.set(e.key, e)
    }
    });
    arr1.forEach(e => {
    if (!map2.has(e.key)) {
    map2.set(e.key, e)
    }
    });
    console.log(map2.values())
    ```
    xiangyuecn
        17
    xiangyuecn  
       143 天前
    // 写了一段 兼容 IE6 🐶
    // 只存在一次两层循环
    // 循环的过程中重新建 2 个数组,数组里面放新的对象,对象里面把原始值存进去,加个计数值

    var arr1=["a","b","c","d","e","f","a","b","a","b"] //字符串意思意思,代替相同的对象
    var arr2=["a","b","c","c","c","c","z","z","z","a"]
    var arr11=[],arr22=[];

    for(var i=0;i<arr1.length;i++){
    arr11.push({value:arr1[i], hit:0});
    }
    for(var i=0;i<arr2.length;i++){
    var obj2={value:arr2[i], hit:0};
    arr22.push(obj2);
    for(var j=0;j<arr11.length;j++){ //给 arr11 计数
    var obj1=arr11[j];
    if(obj1.value==obj2.value){ //自行比较两个对象是否相等
    obj1.hit++;
    obj2.hit++;
    }
    }
    }

    //得到已存在的结果
    arr2.length=0; //?
    for(var i=0;i<arr22.length;i++){
    if(arr22[i].hit){
    arr2.push(arr22[i].value);
    }
    }
    //添加缺失的
    for(var i=0;i<arr11.length;i++){
    if(!arr11[i].hit){
    arr2.push(arr11[i].value);
    }
    }

    console.log(arr2);
    YuJianrong
        18
    YuJianrong  
       142 天前
    @FishBear 作为作者,我要说明一下 fast-array-diff 不是用在这个场景的。
    fast-array-diff 是为了找出一个有序系列转换到另一个有序系列的步骤。
    这个问题的场景是无序的。
    1835407125
        19
    1835407125  
       142 天前
    已经 O(n)了,要是排序好的数组,应该还能优化
    zhj0326
        20
    zhj0326  
       142 天前
    arr2.filter(i => !arr1.includes(i)).forEach(i => {
    const index = arr1.indexOf(i);
    if (index !== -1) {
    arr1.splice(index, 1);
    } else {
    arr1.push(i);
    }
    });
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2692 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 12:20 · PVG 20:20 · LAX 04:20 · JFK 07:20
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.