在数组列表中搜索出现最频繁的字符串

Question

我想知道如何搜索一个String的ArrayList，以找到我创建的'行程'对象中最常出现的“目的地”（包含不同目的地的列表）。

目前为止我有：

public static String commonName(ArrayList<Itinerary> itinerary){

    int count = 0;
    int total = 0;

    ArrayList<String> names = new ArrayList<String>();
    Iterator<String>itr2 = names.iterator();

    while(itr.hasNext()){ 

        Itinerary temp = itr.next();  

        if(temp.iterator().hasNext()){ //if its has destinations

                // Destination object in itinerary object 
                Destination temp2 = temp.iterator().next(); 
                String name = temp2.getDestination().toLowerCase().replace(" ", "");

                if(names.contains(name)){
                    count = count + 1;
                    //do something with counting the occurence of string name here
                }

我正在尝试编写一个算法，以便在数组中搜索最常出现的字符串，如果有并列的，则搜索所有这些字符串，并显示它们所在的'Itinerary object'（参数值）的编号。任何帮助都将是极好的，谢谢！

- LeighA

---

在每行代码旁边添加描述Java代码含义的注释并不实用，事实上这样做会分散注意力，也不美观。 - Paul Tomblin

补充Paul的观点，当你更改代码但不更新注释以反映更改时，情况会变得非常糟糕。 - mfeingold

Answer 1

我会创建一个 HashMap<String,Integer>。然后我会遍历每个行程，如果目的地不在Map中，我会使用put(destination, 1)创建一个条目，否则我会使用put(destination, get(destination)+1)增加已有计数。之后，我会遍历Map条目并查找计数最高的那一个。

- Paul Tomblin

---

这可能不是最高效的（基于CPU周期），但它绝对是首先想到的代码最少的方法来完成工作。+1。 - Dean J

如果在执行get(destination)+1步骤时保持'max'值并递增它，则可以跳过最后一步（运行地图条目并查找最高计数）。如果新值大于以前看到的任何值，则存储指向该条目的指针。（我认为这是最快的解决方案，因为它是O(n)。肯定比排序快，排序是nLogn） - user244277

我的解决方案是O(N) - 你只需遍历一次行程列表，然后再遍历一次找到的目的地列表。 - Paul Tomblin

Answer 2

在统计学中，这被称为“众数”。一个普通的Java 8解决方案看起来像这样：

itinerary
      .stream()
      .flatMap(i -> StreamSupport.stream(
          Spliterators.spliteratorUnknownSize(i.iterator(), 0)
      ))
      .collect(Collectors.groupingBy(
          s -> s.getDestination().toLowerCase().replace(" ", ""), 
          Collectors.counting()
      ))
      .entrySet()
      .stream()
      .max(Comparator.comparing(Entry::getValue))
      .ifPresent(System.out::println);

jOOλ是一个支持在流上使用mode()的库。以下是示例程序：

System.out.println(
    Seq.seq(itinerary)
       .flatMap(i -> Seq.seq(i.iterator()))
       .map(s -> s.getDestination().toLowerCase().replace(" ", ""))
       .mode()
);

（免责声明：我是 jOOλ 背后公司的员工）

- Lukas Eder

Answer 3

如果您不介意使用外部jar包，您可以使用apache commons中的HashBag轻松完成此操作。

public static String commonName(ArrayList<Itinerary> itinerary){

int count = 0;
int total = 0;
Bag names = new HashBag();

while(itr.hasNext()){ //while array of Itinerary object has next
    Itinerary temp = itr.next();  //temp = 1st itineray object
    if(temp.iterator().hasNext()){ //if its has destinations
            Destination temp2 = temp.iterator().next(); //n Destination object in itinerary object 
            String name = temp2.getDestination().toLowerCase().replace(" ", "");
            names.add(name, 1);
    }
}

然后稍后您可以调用 names.getCount("destination1") 来获取 destination1 出现的次数

请参见 http://commons.apache.org/collections/userguide.html#Bags

- royalsampler

---

非常感谢大家的快速和有用的回答！我刚开始学习Java，虽然我以前没有使用过HashBag，但我一定会在Java API中查找它！再次感谢！ - LeighA

Answer 4

尝试使用lambdaj库的分组功能。为解决您的问题，您可以根据目的地属性对Itinerary对象进行分组，然后找出具有最大大小的组，例如以下示例：

Group<Sale> group = selectMax(group(itineraries, 
    by(on(Itenarary.class).getDestination())).subgroups(), on(Group.class).getSize());

- Mario Fusco