3

我在从 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 类属性。

更新：我应该提到我只允许在这部分分配中使用基于动态索引的存储，这意味着没有基于哈希的存储。

4

5 回答 5

5

由于这是一项作业，我不打算编写代码。但是，我建议采用不同的方法。

  • 在你做的时候遍历数组
  • 使用该subList()方法构造数组从开始到但不包括当前元素的视图
  • 用于contains()测试当前元素是否在上一步构建的子列表中
  • 只计算找到了多少不包含在前缀中的元素

我推荐的方法应该会产生更简单和更容易理解的代码。请注意，所有这些都是 O(n 2 ) 解决方案（如果您做对了，您的解决方案也是如此）。

如果赋值允许修改数组，另一种方法是对数组进行排序。然后相等的元素将是相邻的，很容易计算有多少是唯一的。这是一种 O(n log(n)) 方法。（您也可以只复制数组，这不会改变渐近复杂度，但会减慢求解速度。）

如果不使用某种散列函数（HashSet或HashMap），你不会比这更好。

于 2012-12-02T16:53:13.077 回答
2

如果您打算使用该方法，那么这就是您的问题：修改 if-then-else 使其不会在第二个循环中添加单词。在内部循环中使用布尔变量验证是否存在重复项，如果没有重复项，则在第二个循环之后将单词添加到列表中。

于 2012-12-02T17:04:08.350 回答
0

如果使用嵌套的 for 循环结构进行迭代，删除每个元素的重复项，然后将剩余元素添加到新数组中，则可以返回一个较小的数组。我不确定这是否是最快的方法，但它确实有效。

// Delete all dupes
for ( i=0; i<words.length; i++ ) {
  String word = words[i];
  for ( j=(i+1); j<words.length; j++) {
     if (words[j] == words[i]) {
        words[j] = null;
     }
  }
}

// Count the array w/o nulls
int countEl = 0;
for (i=0; i<words.length; i++) {
  if (words[i] != null) {
     countEl++;
  }
}

// Make a new array
String[] newArray = new String[countEl];

for (i=0; i<words.length; i++) {
  if (words[i] != null) {
    countEl.push(words[i]);
  }
}
于 2012-12-02T17:01:30.893 回答
0

您应该通过调用arraylist 上的contains()方法来检查重复项，而不是运行整个长度的循环。

  word.subList(fromIndex, toIndex).contains(arg);

这样你的代码会非常简洁。

于 2012-12-02T16:56:08.480 回答
0

如果你想让它更简单，试试这个

final ArrayList duplicateWords = new ArrayList() ;
ArrayList<String> words = new ArrayList() {
    @Override
    public boolean add(Object e) {
        if( !contains(e) ) {
        return super.add(e);
        } else {
            duplicateWords.add(e);
            return false ;
        }
    }
};
System.out.println("Unique words : " + words.size());
System.out.println("Duplicate words : " + duplicateWords.size());

这是一个替代答案。

于 2012-12-02T17:06:32.507 回答