Java实现：替换列表中与目标列表不匹配的元素

原代码错误原因 #

原代码中，对于每个位置j，会遍历当前子列表的所有匹配位置k：只要j不等于其中某一个k，就执行替换操作。但即使j是匹配位置，当k遍历到其他匹配位置时，j != k的条件也会成立，导致匹配位置的元素被反复替换，最终所有元素都被修改了。

正确实现方案 #

有两种简洁的实现方式：

方式1：利用已有的positionsList #

将每个子列表的匹配位置转成Set（提升查询效率），遍历每个位置时，判断该位置是否不在匹配集合中，若是则替换：

// 遍历每个子列表
for (int i = 0; i < population.size(); i++) {
    // 将匹配位置列表转为Set，方便快速查询
    Set<Integer> matchedPositions = new HashSet<>(positionsList.get(i));
    ArrayList<String> currentSong = population.get(i);
    
    // 遍历每个位置
    for (int j = 0; j < song.size(); j++) {
        // 如果当前位置不在匹配集合中，替换为随机音符
        if (!matchedPositions.contains(j)) {
            currentSong.set(j, notes.get(rand.nextInt(notes.size())));
        }
    }
}

方式2：直接对比原目标列表（无需依赖positionsList） #

这种方式更简洁，不需要提前存储匹配位置，直接实时对比song和当前子列表的元素，不相等则替换：

// 遍历每个子列表
for (int i = 0; i < population.size(); i++) {
    ArrayList<String> currentSong = population.get(i);
    
    // 遍历每个位置
    for (int j = 0; j < song.size(); j++) {
        // 如果当前元素和目标song的对应元素不相等，替换为随机音符
        if (!song.get(j).equals(currentSong.get(j))) {
            currentSong.set(j, notes.get(rand.nextInt(notes.size())));
        }
    }
}

额外优化建议 #

• 生成随机数时，如果使用Random类，建议将rand实例声明为类成员变量，避免循环内重复创建。
• 若population规模较大，方式1中的HashSet能有效降低查询匹配位置的时间复杂度（从O(n)变为O(1)）。

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