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，理想情况下包含、获取、放置操作具有 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();
}

Answer 2

这里有一个简单的建议：

1. 首先，按字母数字顺序对数组进行排序
2. 循环遍历，if( !list.get(i).equals(list.get(i+1)) ) → unique
3. 如果发现重复项，请递增i，直到到达其他字符串

这将具有排序算法的复杂性，因为步骤 2+3 应该是 O（n）

Answer 3

使用ArrayList有什么特殊需求吗？您可以使用HashSet轻松完成此操作。

以下是代码片段：

public static void main (String[] args) {
    String[] words = {"foo","bar","foo","fo","of","bar","of","ba","of","ab"};
    Set<String> set = new HashSet<>();
    Set<String> common = new HashSet<>();
    for (String i : words) {
        if(!set.add(i)) {
            common.add(i);
        }
    }
    System.out.println(set.size() - common.size());
}

输出：

3

以下是修改后的代码：

public static int countNonRepeats(WordStream words) {
    Set<String> set = new HashSet<>();
    Set<String> common = new HashSet<>();
    for (String i : words) {
        if(!set.add(i)) {
            common.add(i);
        }
    }
    return (set.size() - common.size());
}

Answer 4

您可以使用哈希图来实现此目的。使用这种方法，我们可以计算所有单词的出现次数，如果我们只对唯一单词感兴趣，
则访问count = 1的元素。
HashMap<String,Integer> - 键表示数组列表中的字符串，整数表示发生次数。

        ArrayList<String> list = new ArrayList<String>();
        HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
        for (int i = 0; i < list.size(); i++) {
            String key = list.get(i);
            if (hashMap.get(key) != null) {
                int value = hashMap.get(key);
                value++;
                hashMap.put(key, value);
            } else {
                    hashMap.put(key, 1);
            }
        }
        int uniqueCount = 0;
        Iterator it = hashMap.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            if ((int) pair.getValue() == 1)
                uniqueCount++;
        }
        System.out.println(uniqueCount);