Java计算已排序数组中每个元素的出现次数

Question

我有一个字符串数组，想要计算任何单个字符串的出现次数。

我已经对它进行了排序。（这是一个很长的数组，我想摆脱O（n²）-loop）

这里是我的代码..显然它在ind.outOfB中运行出错..原因很清楚，但我不知道如何解决..

for (int i = 0; i < patternsTest.length-1; i++) {
        int occ=1;
        String temp=patternsTest[i];
        while(temp.equals(patternsTest[i+1])){
            i++;
            occ++;
        }
    }

- Jan S

---

为什么不使用 Map<String, Integer>？ - Franklin

我需要原始计数... 我不知道是否只为此创建一个Map... - Jan S

为什么不呢？这样做会更快，而且未来修改也更容易。 - Franklin

你不想使用Map来提高效率吗？通过排序，你会失去很多效率，而使用Map意味着你不需要预先排序。但如果你真的不想使用Map，只需解释原因，或者直接说出来就可以了 :) - greedybuddha

Answer 1

这里适合使用HashMap，键应该是单词，值应该是它出现的次数。使用Map.containsKey和Map.get方法进行常量时间查找，非常快速。

Map<String,Integer> map = new HashMap<String,Integer>();
for (int i = 0; i < patternsTest.length; i++) {
    String word=patternsTest[i];
    if (!map.containsKey(word)){
        map.put(word,1);
    } else {
        map.put(word, map.get(word) +1);
    }
}

作为一个额外的好处，甚至不需要事先进行排序！

- greedybuddha

---

但是 .containsKey() 会遍历整个 Map 吗？而且每次都会覆盖现有的条目..? 这样似乎效率不高.. 不是说这是一种不好的方法.. - Jan S

containsKey是O(1)搜索。这意味着它不会遍历整个映射，更像是索引到数组而不是完全搜索。我也会用这个更新答案。 - greedybuddha

好问题 :P .. 大家都在寻找最快的方法，对吧？;) 到目前为止已经足够了.. 我认为我的方法的工作版本会更慢.. 因为需要排序等操作。非常感谢 :) - Jan S

从你删除了我无法评论的上一个回答中：依我看，这个问题可以开放并回答，但不能直接给出代码或直接解决方案，而是引导提问者理解如何解决。请参考 如何提问和回答作业问题？。 - Luiggi Mendoza

他已经展示了一些努力和代码，这让我对他的行为不那么反感。在我看来，给出一个算法是一个公平的提示，但在这种情况下，算法有很多解决方案，所以我只是添加了它。最终，我同意你的观点，所以我删除了答案。现在还是早上，有时候我会自动进入工作模式；）不过，你提供的链接很好，我将来会用它来评论类似这样的问题。 - greedybuddha

Answer 2

您可以使用Java HashMap：

Map<String, Integer> occurrenceOfStrings = new HashMap<String, Integer>();

for(String str: patternsTest)
{
    Integer currentValue = occurrenceOfStrings.get(str);
    if(currentValue == null)
        occurrenceOfStrings.put(str, 1);
    else
        occurrenceOfStrings.put(str, currentValue + 1);
}

- taocp

Answer 3

这个没有索引越界：

String[] patternsTest = {"a", "b"};
for (int i = 0; i < patternsTest.length-1; i++) {
    int occ=1;
    String temp=patternsTest[i];
    while(temp.equals(patternsTest[i+1])){
        i++;
        occ++;
    }
}

如果将数据更改为以下内容，可能会导致索引越界：

String[] patternsTest = {"a", "a"};

- ashatch

Answer 4

你可以尝试使用一个映射表和仅有的一个循环。

Map<String, Integer> occurences = new HashMap<String, Integer>();
String currentString = patternsTest[0];
Integer count = 1;

for (int i = 1; i < patternsTest.length; i++) {
    if(currentString.equals(patternsTest[i]) {
        count++;
    } else {
        occurrences.put(currentString, count);
        currentString = patternsTest[i];
        count = 1;
    }
}
occurrences.put(currentString, count);

- Marco Forberg

Answer 5

我的解决方案是：

public int cantOccurences(String pattern, String[] values){
  int count = 0;

  for (String s : values) {
    count +=  (s.replaceAll("[^".concat(pattern).concat("]"), "").length());
  }
return count;
}

- Gere

Answer 6

Guava Multiset解决方案（两行代码）：

Multiset<String> multiset = HashMultiset.create();
multiset.addAll(Arrays.asList(patternsTest));

//Then you could do...
multiset.count("hello");//Return count the number of occurrences of "hello".

我们可以在排序和未排序的数组中使用它。代码易于维护。

- 卢声远 Shengyuan Lu