从字符数组生成无重复字符列表时remove方法失效问题排查

问题描述 #

执行代码中的nonReps.remove(indexInNonreps);语句时，无法按预期删除指定索引的元素，最终输出结果与预期不符。

原代码 #

// given an array
Character[] arr = new Character[]{'a','a','a','b','c','c','c','d','e','e','e','f'};

Map<Character, Integer> map = new HashMap<>();
List<Character> nonReps = new ArrayList<>();

for (int i = 0; i < arr.length; i++) {
    if (map.containsKey(arr[i])) {
        Integer indexInNonreps = map.get(arr[i]);
        Character characterInNonreps = nonReps.get(indexInNonreps);

        if (arr[i].equals(characterInNonreps))
            nonReps.remove(indexInNonreps);
    } else {
        nonReps.add(arr[i]);
        map.put(arr[i], nonReps.size()-1);
    }
}

System.out.println(nonReps);

实际输出 #

[a, b, c, d, e, f]

预期输出 #

[b, d, f]

问题原因 #

1. 索引失效：ArrayList删除元素后，后续元素的索引会自动前移，但你在Map中存储的是元素的旧索引。后续再次获取该索引时，指向的已经不是目标元素，导致arr[i].equals(characterInNonreps)判断不成立，无法触发删除。
2. 重复元素未彻底清理：即使第一次删除了重复元素，你没有从Map中移除对应的键。后续再次遇到该元素时，依然会进入判断分支，但此时列表中已无该元素，索引匹配失败，无法执行删除。

修正方案 #

方案一：简化标记逻辑（避免维护索引） #

用Map标记元素是否已添加，直接通过元素值删除，无需维护索引：

Character[] arr = new Character[]{'a','a','a','b','c','c','c','d','e','e','e','f'};

Map<Character, Boolean> isAdded = new HashMap<>();
List<Character> nonReps = new ArrayList<>();

for (Character c : arr) {
    if (isAdded.containsKey(c)) {
        // 元素重复，从列表移除
        nonReps.remove(c);
        // 标记为已处理重复
        isAdded.put(c, false);
    } else {
        // 首次出现，添加到列表并标记
        nonReps.add(c);
        isAdded.put(c, true);
    }
}

System.out.println(nonReps); // 输出 [b, d, f]

方案二：先统计次数再筛选（逻辑更清晰） #

先统计每个元素的出现次数，再筛选出仅出现一次的元素：

Character[] arr = new Character[]{'a','a','a','b','c','c','c','d','e','e','e','f'};

Map<Character, Integer> countMap = new HashMap<>();
// 统计所有元素出现次数
for (Character c : arr) {
    countMap.put(c, countMap.getOrDefault(c, 0) + 1);
}

// 筛选仅出现一次的元素
List<Character> nonReps = new ArrayList<>();
for (Character c : arr) {
    if (countMap.get(c) == 1 && !nonReps.contains(c)) {
        nonReps.add(c);
    }
}

System.out.println(nonReps); // 输出 [b, d, f]

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