Java 对已字母序排序的字符串ArrayList去重后仍残留重复元素的问题排查
问题根因
逻辑硬伤
- 你的ArrayList是已按字母序排好的有序列表,这类列表的重复元素必然相邻,根本不需要每次删除元素后把i重置为0从头全量扫。你代码里删完重复就把i设为0的操作,完全是多余的,还引入了致命的索引偏移bug。
- for循环的执行逻辑是固定的:循环体跑完就自动执行
i++。你删完i+1位置的重复元素后把i赋值为0,循环会立刻执行i++把i变成1,导致后续扫描的起点直接从索引1开始,永久漏判索引0位置和后续元素的重复校验。只要列表头部有连续重复,就一定会残留未去重的内容。 - 举个最小复现:输入列表
["A", "A", "A", "B"]跑原代码的流程:- i=0时发现前两个A相等,删掉索引1的元素,列表变成
["A", "A", "B"],此时i被赋值为0 - 循环体执行完,自动跑i++,i变成1
- 后续循环从i=1开始,对比第二个A和B没有差异,最后列表就会残留两个A的重复
- i=0时发现前两个A相等,删掉索引1的元素,列表变成
- 你看到列表里残留两个AGE,本质就是同样的漏判:某次删除操作触发i重置后,扫描节奏被打乱,刚好跳过了两个相邻AGE的对比分支,最终重复元素留下来了。
- 额外的问题:每次删完就从头全量扫的写法时间复杂度是O(n²),长列表下性能损耗极大,完全没必要。
可行解决方案
针对当前有序ArrayList的去重场景,两种实现都比原代码简洁高效,还不会有漏判问题:
方案1:从后往前遍历删除(逻辑最直观,无索引偏移)
从后往前遍历时,删掉当前位置的元素不会影响前面未遍历部分的索引,完全不会出现漏判:
public static void removeDuplicate(ArrayList<String> array){ // 从列表最后一个元素往前遍历,直到第一个元素 for (int i = array.size() - 1; i > 0; i--) { // 对比当前元素和相邻的前一个元素,命中重复就删当前元素 if (array.get(i).equalsIgnoreCase(array.get(i-1))) { array.remove(i); } } }
方案2:正向遍历+动态控制索引(O(n)时间复杂度)
不需要重置i到0,只要删完重复元素不递增索引,让前移补位的元素继续和当前位置对比,就能连续清掉所有相邻重复:
public static void removeDuplicate(ArrayList<String> array){ int i = 0; // 只要还有相邻元素就继续对比 while (i < array.size() - 1) { if (array.get(i).equalsIgnoreCase(array.get(i+1))) { // 相邻重复,删掉后一个元素,此时i不递增,留着下轮对比补位的新元素 array.remove(i+1); } else { // 没重复才往前挪索引 i++; } } }
注意:如果是未排序的无序列表,上面的实现无法完成全量去重,需要配合HashSet处理;但当前场景是已排序的列表,这两种实现都是最优解。
内容的提问来源于stack exchange,提问作者Ryan。
相关产品推荐
相关产品推荐

