Groovy中高效检测Map内多列表间重复元素并终止处理的实现方法

嘿，这个场景我太熟悉了——双重遍历两两比对确实效率拉胯，尤其是列表多、元素量大的时候。其实我们可以换个思路：用全局集合追踪已出现的元素，只需要一次遍历就能完成检测，时间复杂度直接从O(n²)降到O(n)，效率提升不是一星半点！

核心思路 #

不需要把每个列表和其他所有列表逐一比对，而是维护一个全局的HashSet（查询和插入都是O(1)复杂度）：

1. 遍历Map中的每个列表
2. 检查当前列表的元素是否已经在全局集合中存在
3. 如果发现重复元素，立刻抛出异常终止流程
4. 如果没有重复，就把当前列表的所有元素加入全局集合，继续下一个列表

这样整个过程只需要遍历所有元素一次，而且一旦发现重复就停止，完全不会做无用功。

具体实现代码 #

先还原你的Map构建：

def list1 = ["val1", "val2", "val3"]
def list2 = ["val7", "val8"]
def list3 = ["val4", "val5", "val2"]
def list4 = ["val6", "val4", "val3"]

def map = [
    key1: list1,
    key2: list2,
    key3: list3,
    key4: list4
]

然后是高效的检测逻辑：

def seenElements = new HashSet<>()

map.each { entry ->
    def currentKey = entry.key
    def currentList = entry.value
    
    // 快速检查当前列表是否有元素已被记录
    def duplicateElements = currentList.intersect(seenElements)
    if (!duplicateElements.isEmpty()) {
        throw new IllegalArgumentException(
            "检测到跨列表重复元素: ${duplicateElements.join(', ')}，列表${currentKey}中的元素与之前的列表重复"
        )
    }
    
    // 将当前列表的所有元素加入全局追踪集合
    seenElements.addAll(currentList)
}

println("所有列表之间无重复元素，验证通过")

更细粒度的优化（可选） #

上面的代码用intersect一次性检查整个列表，如果你想在遇到第一个重复元素时就立刻抛出异常（不用等整个列表检查完），可以用更细粒度的遍历：

def seenElements = new HashSet<>()

map.each { currentKey, currentList ->
    currentList.each { element ->
        // HashSet的add方法会返回false，如果元素已经存在
        if (!seenElements.add(element)) {
            throw new IllegalArgumentException(
                "元素'${element}'重复！列表${currentKey}中的该元素已在之前的列表中出现过"
            )
        }
    }
}

这个版本会在发现第一个重复元素时立刻终止，在某些场景下（比如重复元素出现在列表开头）会比intersect更快。

为什么这个方案更高效？ #

• 时间复杂度：原来的双重遍历是O(m²*k)（m是列表数量，k是平均每个列表的元素数），现在的方案是O(totalElements)，总元素数固定的话，效率提升非常明显
• 提前终止：一旦发现重复就立刻抛出异常，不会继续遍历剩余元素
• HashSet的优势：HashSet的contains和add操作都是常数时间复杂度，比列表比对快得多

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