Java ArrayList删除没有集合的dupes

Question

我在从ArrayList中删除重复项时遇到问题.这是为了大学的任务.这是我已经拥有的代码:

public int numberOfDiffWords() {
    ArrayList<String> list = new ArrayList<>();
    for(int i=0; i<words.size()-1; i++) {
        for(int j=i+1; j<words.size(); j++) {
            if(words.get(i).equals(words.get(j))) {
                // do nothing
            }
            else  {
                list.add(words.get(i));
            }
        }
    }
    return list.size();
}

问题出在numberOfDiffWords()方法上.填充列表方法工作正常,因为我的讲师给了我一个样本字符串(包含4465个单词)进行分析 - 打印words.size()给出了正确的结果.

我想返回新ArrayList的大小,删除所有重复项.

words 是一个ArrayList类属性.

更新:我应该提到我只允许在分配的这一部分使用基于动态索引的存储,这意味着没有基于散列的存储.

Answer 1

由于这是一项任务,我不打算编写代码.但是,我建议采用不同的方法.

• 正如你所做的那样遍历数组
• 使用该subList()方法从一开始就构造一个数组视图,但不包括当前元素
• 用于contains()测试当前元素是否在上一步构建的子列表中
• 只计算找到的前缀中未包含的元素数量

我推荐的方法应该会产生更简单易懂的代码.请注意,所有这些都是O(n ²)解决方案(正如您的解决方案一样).

如果分配允许修改数组,则另一种方法是对数组进行排序.然后相等的元素将相邻,并且很容易计算有多少是唯一的.这是一种O(n log(n))方法.(您也可以只创建一个数组副本,这不会改变渐近的复杂性,但会降低解决方案的速度.)

如果不使用某种(HashSet或HashMap)散列函数,你将不会比这更好.