遍历列表时移除元素的最优实现及合并重叠区间代码的优化咨询

阿华AIGC实验室

2026-3-31

你的现有代码确实能完成合并重叠区间的工作，手动调整索引i--也能解决删除元素后跳过项的问题，但这种嵌套循环+手动维护索引的写法确实不够直观，而且时间复杂度是O(n²)，当列表规模变大时效率会下降。我给你推荐两种更优雅且高效的实现方式：

方案一：排序后线性遍历合并（最优推荐）

这是处理重叠区间问题的经典高效写法，核心思路是先把所有区间按起始值排序，这样我们只需要一次遍历就能完成合并，完全不需要处理复杂的索引删除逻辑：

private void reconcile() {
    if (list.isEmpty()) {
        return;
    }
    // 先按区间的start值升序排序（假设你的自定义对象有getStart()方法）
    list.sort(Comparator.comparingInt(YourRangeClass::getStart));
    
    List<YourRangeClass> merged = new ArrayList<>();
    merged.add(list.get(0));
    
    for (YourRangeClass current : list) {
        YourRangeClass lastMerged = merged.get(merged.size() - 1);
        if (current.overlaps(lastMerged)) {
            // 重叠则调用merge方法合并
            lastMerged.merge(current);
        } else {
            // 不重叠直接加入结果列表
            merged.add(current);
        }
    }
    
    // 如果需要替换原列表，直接覆盖即可
    list.clear();
    list.addAll(merged);
}

为什么这种写法更优？

时间复杂度降到了O(n log n)（主要耗时在排序环节），数据量大时比原O(n²)写法效率提升明显
完全规避了遍历原列表时删除元素的索引混乱问题，逻辑清晰易懂
不需要手动维护i--这种容易出错的索引调整，可读性和可维护性都拉满

方案二：用迭代器原地修改（适合必须操作原列表的场景）

如果你因为业务限制必须在原列表上直接修改（而不是生成新列表），可以用Iterator来遍历并删除元素，JDK会帮我们自动处理索引问题，搭配排序依然能保证高效：

private void reconcile() {
    if (list.size() < 2) {
        return;
    }
    // 先排序，后续遍历逻辑会更简单
    list.sort(Comparator.comparingInt(YourRangeClass::getStart));
    
    Iterator<YourRangeClass> iterator = list.iterator();
    YourRangeClass prev = iterator.next();
    
    while (iterator.hasNext()) {
        YourRangeClass current = iterator.next();
        if (prev.overlaps(current)) {
            prev.merge(current);
            // 用迭代器的remove方法删除当前元素，无需手动调整索引
            iterator.remove();
        } else {
            prev = current;
        }
    }
}