java - 在不使用 HashMap 的情况下查找排序的 ArrayList 中最常见的字符串

Question

考虑包含 String 的 ArrayList

animalsArray[dog, cat, dog, dog, cat, duck, duck, dog]

我可以轻松地使用 HashMap 来查找最常见的 String，使用 HashMap 值作为计数器，并使用键来查找最常见的 String。存储动物名称。

如果 ArrayList 已排序

[dog, dog, dog, dog, cat, cat, duck, duck]

在不使用Hashmap的情况下查找最常见元素的最简单方法是什么？我正在考虑使用 for 循环将 animalArray.get(i) 与 animalArray.get(i-1) 进行比较，但我无法开发此解决方案。当我们需要查找最常见的元素时，使用排序的 ArrayList 有哪些优点(如果有)？

Answer 1

What is the easiest way to find the most common element without using Hashmaps?

我认为(Java 8+)这非常简单:

String str = list.stream()
                 .distinct()
                 .max(Comparator.comparing(e -> Collections.frequency(list, e)))
                 .get();

这将创建List的Stream，并查找List中出现频率最高的元素。

And what are the advantages, if there are any, of having a sorted ArrayList when we need we need to find the most common element?

想象一个未排序的列表:

[dog, cat, turtle, cat, dog, snake]

对于每个元素，您都必须搜索 List 的其余部分以查看它出现的次数。

但是使用排序的列表:

[dog, dog, cat, cat, snake, turtle]

您只需要有一个计数器来跟踪包含相同元素的最长子列表。然后它变成类似(伪代码)的东西:

//T being the type of the List
T element
int count = 0;
int biggestCount = 0;
for(every element in the list) {
   if the item is the same as previous
      count++
   else 
      //Only check when we're about to change elements
      if count > biggestCount
          biggestCount = count
          element = current element of List
      //Starting over with a new element
      count = 1
}
return element