Java:如何计算ArrayList中不重复(只出现一次)的字符串？

Question

我正在尝试查找在 ArrayList 中仅出现一次的字符串数量。

我有多少人实现了这一目标(最好以尽可能最佳的时间复杂度)？

下面是我的方法:

  public static int countNonRepeats(WordStream words) {

    ArrayList<String> list = new ArrayList<String>();
    for (String i : words) {
      list.add(i);
    }

    Collections.sort(list);

    for (int i = 1; i < list.size(); i++) {
      if (list.get(i).equals(list.get(i - 1))) {
        list.remove(list.get(i));
        list.remove(list.get(i - 1));
      }
    }

    System.out.println(list);

    return list.size();
  }

为什么它不删除 list.get(i) 和 list.get(i-1) 处的字符串？

Answer 1

不需要排序。更好的方法是使用两个 HashSet，一个用于维护重复单词，一个用于非重复单词。由于HashSet内部使用HashMap，理想情况下包含、get、put操作的复杂度为o(1)。因此该方法的总体复杂度为 o(n)。

    public static int countNonRepeats(List<String> words) {

    Set<String> nonRepeating = new HashSet<String>();
    Set<String> repeating = new HashSet<String>();


    for (String i : words) {
        if(!repeating.contains(i)) {
            if(nonRepeating.contains(i)){
                repeating.add(i);
                nonRepeating.remove(i);
            }else {
                nonRepeating.add(i);
            }
        }
    }

    System.out.println(nonRepeating.size());

    return nonRepeating.size();
}