基于Iterator的纸牌匹配游戏算法效率评估及优化咨询

当前实现的问题 #

• 效率不合格：每次调用方法都需要完整拷贝一次输入列表，额外占用O(n)空间；双层迭代循环导致单次扫描时间复杂度为O(n²)，列表长度较大时性能损耗非常明显。
• 存在逻辑bug：你通过原列表迭代器和拷贝列表迭代器同步位置，但原列表删除元素后结构发生变化，两个迭代器的位置会出现错位，极端场景下会抛出NoSuchElementException，连续匹配多对元素的场景下很容易触发。

优化实现方案 #

我们可以用单次遍历+临时列表的思路实现，不需要拷贝全量列表做同步，也不需要双层循环，逻辑更简单，性能更高，同时完全满足仅使用Iterator的要求：

辅助匹配方法（参考实现） #

// 判断两个两位数是否满足首位/末位匹配可移除条件
private static boolean removable(int a, int b) {
    int aFirst = a / 10, aLast = a % 10;
    int bFirst = b / 10, bLast = b % 10;
    return aFirst == bFirst || aFirst == bLast || aLast == bFirst || aLast == bLast;
}

优化后的scanAndRemovePairs方法 #

public static boolean scanAndRemovePairs(ArrayListWithIterator<Integer> theList) {
    boolean pairsRemoved = false;
    // 临时列表存储当前未匹配的元素
    ArrayListWithIterator<Integer> tempList = new ArrayListWithIterator<>(theList.getLength());
    Iterator<Integer> iterator = theList.getIterator();

    while (iterator.hasNext()) {
        Integer current = iterator.next();
        // 临时列表不为空时，比对当前元素和临时列表最后一个元素
        if (tempList.getLength() > 0) {
            Integer lastInTemp = tempList.get(tempList.getLength() - 1);
            if (removable(lastInTemp, current)) {
                // 匹配则移除临时列表最后一个元素，不加入当前元素
                tempList.remove(tempList.getLength() - 1);
                pairsRemoved = true;
                continue;
            }
        }
        // 不匹配则加入临时列表
        tempList.add(current);
    }

    // 用处理后的临时列表覆盖原列表
    theList.clear();
    for (Integer num : tempList) {
        theList.add(num);
    }

    return pairsRemoved;
}

优化点说明 #

• 空间复杂度：仅额外使用一个临时列表，且临时列表的最大长度和输入列表一致，和原有实现空间复杂度持平，但没有多余的全量列表拷贝开销。
• 时间复杂度：单次扫描仅需一次遍历，时间复杂度为O(n)，整体最坏情况下（每次仅移除一对元素需要重扫n次）时间复杂度为O(n²)，但常数项远低于原有双层循环的实现，实际运行效率提升非常明显。
• 逻辑稳定性：没有迭代器同步错位的问题，不会出现并发修改异常或元素找不到的问题，适配所有边界场景（空列表、全匹配列表、无匹配列表等）。
• 原有Main方法不需要做任何修改，直接替换scanAndRemovePairs实现即可正常运行。

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