如何仅返回最少次数出现的字符串ArrayList？

Question

我有一个String[]数组，名为originalStringArray，其中含有重复项，例如{"dog","cat","dog","fish","dog","cat"}。

我想创建一个函数，只返回出现了特定次数的字符串。例如，如果我输入3，它会返回"dog"，但不会返回"cat"。

以下是我当前的代码：

public ArrayList<String>  returnMultiples(String[] originalStringArray,int requiredCount){
    ArrayList<Integer> mCount = new ArrayList<>();
    List<String> list = Arrays.asList(originalStringArray);
    ArrayList<String> result = new ArrayList<>();

    // Count occurrences in original string
    for(String item: originalStringArray){
        mCount.add(Collections.frequency(list,item));
    }

    // If frequency is equal to count, add to array list
    for(int i=0; i<mCount.size(); i++){
        if(mCount.get(i) == requiredCount){
            result.add(originalStringArray[i]);
        }
    }

    return result;
}

我遇到的问题是，我在某个地方读到说Collections库非常慢且拖累，并且似乎可以使用HashSets和tables来减少这种情况。不幸的是，我有些茫然，不知道该如何做。有没有更好的方法来解决这个问题？

- Kat

---

展示一个引用。Java集合库经过高度优化。那些说它们慢的人通常没有正确使用它们。你是对的。你想要一个Map<String, Integer>来解决这个问题。特别是，如果你想保持原始出现顺序，使用一个OrderedHashMap。 - Gene

在我看来，如果你处理的数据量很小，性能并不是很重要。但当你处理成千上万个元素时，性能就开始变得重要了，即使在这种情况下也只有一点点。话虽如此，你不能使用集合，因为每个集合元素必须是唯一的。我会在初始数组循环中将每个元素及其出现次数插入到哈希映射表中。然后，你需要循环遍历哈希映射表，并获取与你的出现次数标准相匹配的键。 - Eric Guan

Multiset是Guava库中专门为此目的设计的东西。 - Mick Mnemonic

@Gene 嗯，坦白地说，引用会是另一个SO问题上的一条评论。不是非常有效的来源。感谢OrderHashMap的想法。 - Kat

Answer 1

需要一种地图来执行此操作。这里使用HashMaps编写了一个示例：

public ArrayList<String> returnMultiples(String[] array, int min){
    HashMap<String, Integer> counts = new HashMap<String, Integer>();//instantiate a new HashMap

    //loop through the array and count the occurrences of each different string in the array
    for(int i = 0; i < array.length; i++){
        String word = array[i];
        if(counts.containsKey(word))
            counts.put(word, counts.get(word) + 1);
        else
            counts.put(word, 1);
    }

    ArrayList<String> multiples = new ArrayList<String>();

    //check if any of the words occur >= min times. if so, add them to the returning list.
    for(String key : counts.keySet()){
        if(counts.get(key) >= min){
            multiples.add(key);
        }
    }

    return multiples;//return the list we just created of the desired strings
}

根据字符串长度的不同，使用HashMap相比于使用集合会更加高效，尽管两者之间的差异基本可以忽略不计。

- rodit

---

@sparkysword 没问题 - 我很高兴能帮助你。 - rodit

你可以使用HashMap的getOrDefault方法，而不是在第一个for循环中使用条件语句。以下是我发布的代码示例。 - Tomasz Dzieniak

Answer 2

你需要使用HashMap来完成这个任务。

假设你的HashMap将包含给定字符串出现次数的计数，因此它的类型将为HasMap<String,Integer>

现在，让我们遍历你的集合：

1. 从集合中获取另一个字符串
2. 检查HashMap中是否存在该字符串（#contains）
3. 如果不存在，则使用字符串键放置新元素（hashMap.put(stringKey,1)；
4. 如果存在，则使用相同的键放置元素，但增加内部计数器（hashMap.put(stringKey,hashMap.get(stringKey)+1)）
5. 继续

现在，您的HashMap包含了来自您的集合中给定字符串的确切出现次数。

快速查找将是创建反向HashMap<Integer,String>，但可能会出现计数重复的情况，这样将无法工作。要获取出现次数匹配给定字符串的字符串，您将不得不遍历映射的所有键，并仅返回满足您条件的那些。

- Antoniossss

Answer 3

我想，使用哈希映射可能是足够有效的。

我能想到的最短的代码（使用HashMap）如下所示：

String[] filter(String[] collection, int requirement) {
    final HashMap<String, Integer> temp = new HashMap<>();

    for (String item : collection) {
        int current = temp.getOrDefault(item, 0);
        temp.put(item, ++current);
    }

    final Iterator<Entry<String, Integer>> iterator = temp.entrySet().iterator();
    while (iterator.hasNext()) {
        final Entry<String, Integer> entry = iterator.next();
        if (entry.getValue() != requirement) {
            iterator.remove();
        }
    }

    return temp.keySet().toArray(new String[temp.size()]);
}

什么可以用于以下内容：

final String[] array = new String[]{
    "dog", "dog", "dog", "cat", "cat", "fish", "cat"
};

final String[] result = filter(array, 3);

for (String item : result) {
    System.out.println(item);
}

并且按预期生成输出：

猫

狗

- Tomasz Dzieniak

Answer 4

你的算法会返回重复项。

HashSet是Collections库的一部分，所以在那里你没有优势。

包含Collections.frequency的循环是一个O(n^2)算法。（对于originalStringArray中的每个字符串，Collections.frequency再次遍历整个originalStringArray）。

你可以只用HashMap来完成这个任务。

为originalStringArray中的每个字符串在map中增加一个Integer。

删除所有值不等于requiredCount的键。

如果你真的想返回一个ArrayList，将map.keySet()添加到一个新的ArrayList中。

或者map.keySet().toArray(String[map.size()])，如果你想要一个数组。

- gary

Answer 5

您可以使用AVL树，前提是如果您的数组中有100万个项目，则需要经过100万步才能遍历该数据结构。而使用AVL树只需要O(Log(1,000,000))步，即6步，非常方便。如果您的数据是动态的，这将是一个不错的方法，尽管您需要优化插入操作。

使用AVL树可以使所有内容都排序，因此可以获得O(Log N)时间。而不是像对于N步骤那样遍历数组：

你可以这样做： ```

你可以这样做：

```

在检查根并看到Char c大于dog中的第一个Char时，它向左遍历。每个步骤基本上将搜索时间缩短了1/2，使其成为O(Log N)步。您必须保持树的高度平衡。 AVL Tree的好处是，由于需要平衡树，因此您的数据始终按排序顺序排列。

如果数据不经常更改且不需要排序数据，则最好使用HashMap。

- AndyRoid

---

哇，感谢您提供如此详细的信息。我听说过很多不同的树，但从未听说过AVL。 - Kat