合并两个Device对象列表去重 实现O(N)时间复杂度方案

你的需求本质是按复合主键去重，且第二个列表的元素优先级高于第一个列表，完全可以通过哈希表一次流程完成，不需要额外提前提取重复集合，整体时间复杂度稳定在线性级别。

原有实现的可优化点 #

你当前的思路存在两个问题：

• 仅用name字段判定重复不符合需求：规则要求name和type同时相等才算重复，单判断name会把同name不同type的设备误判为重复项
• 流程冗余：先提取重复name集合、再合并总列表、最后遍历过滤，多做了两次全量遍历，且循环内的状态判断也有额外开销

补充说明：HashSet.contains()本身平均时间复杂度就是O(1)，你原来的实现整体其实已经是线性复杂度，只是逻辑绕、常数开销高，还存在判定逻辑漏洞。

最优实现思路 #

直接用哈希表存储设备，用name+type的组合作为唯一键，利用哈希表写入时的覆盖特性天然实现优先级规则：

1. 初始化一个空哈希表，key为设备复合唯一键，value为Device对象本身
2. 先遍历第一个列表，把所有设备按唯一键存入哈希表
3. 再遍历第二个列表，把所有设备按相同规则存入哈希表：如果键已存在（即重复项），第二个列表的设备会直接覆盖第一个列表的对应值，正好满足「重复项保留第二个列表status」的要求；如果键不存在则直接新增
4. 最后把哈希表的所有value导出为列表，就是你要的合并结果

整个流程所有操作的平均时间复杂度都是O(1)，总时间复杂度为O(len(list1) + len(list2))，也就是标准的O(N)线性复杂度，没有多余步骤。

参考实现代码 #

import java.util.*;

class Device {
    String name;
    String type;
    String status;

    public Device(String name, String type, String status) {
        this.name = name;
        this.type = type;
        this.status = status;
    }

    // 生成去重专用的复合唯一键，用特殊分隔符避免字段拼接冲突
    private String buildUniqueKey() {
        return String.join("||", name, type);
    }

    @Override
    public String toString() {
        return "{" + name + "," + type + "," + status + "}";
    }
}

class MergeUtils {
    public static List<Device> merge(List<Device> firstList, List<Device> secondList) {
        Map<String, Device> deviceHolder = new HashMap<>();
        // 先放入低优先级的第一个列表
        for (Device d : firstList) {
            deviceHolder.put(d.buildUniqueKey(), d);
        }
        // 放入高优先级的第二个列表，重复项自动覆盖
        for (Device d : secondList) {
            deviceHolder.put(d.buildUniqueKey(), d);
        }
        return new ArrayList<>(deviceHolder.values());
    }

    // 测试验证
    public static void main(String[] args) {
        List<Device> list1 = Arrays.asList(
                new Device("d1","m1","active"),
                new Device("d2","m2","active"),
                new Device("d3","m3","active")
        );
        List<Device> list2 = Arrays.asList(
                new Device("d2","m2","paused"),
                new Device("d4","m4","paused")
        );
        // 输出结果正好符合预期：[{d1,m1,active}, {d2,m2,paused}, {d3,m3,active}, {d4,m4,paused}]
        System.out.println(merge(list1, list2));
    }
}

可选优化 #

如果不想用字符串拼接做键，可以自定义一个静态内部类作为键，只要正确重写equals()和hashCode()方法、把name和type作为判断相等的字段即可，严谨性更高，适合生产环境使用。

内容的提问来源于stack exchange，提问作者amar2108