4

I was wondering how I could search an ArrayList of Strings to find the most commonly occurring 'destination' in an 'Itinerary' object I've created (which contains a list of different destinations.)

So far I have:

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
                }

I'm having problems making an algorithm to search the array for the most commonly occurring string, or strings if there is a tie; and then displaying the number of the 'Itinerary object' (the parameter value) the string is found in. Any help would be great, thank you!!

2
  • Adding a comment to each line describing in words exactly what the Java code says is not useful, as a matter of fact it's distracting and ugly. Feb 18, 2010 at 19:57
  • To add to Paul's argument it becomes a disaster when you change the code but do not update the comment to reflect the changes
    – mfeingold
    Feb 18, 2010 at 20:07

4 Answers 4

8

I would make a HashMap<String,Integer>. Then I would go through each itinerary, and if the destination wans't in the Map I would create an entry with put(destination, 1), otherwise I would increment the count that was there with put(destination, get(destination)+1). Afterwards I'd go through the Map entries and look for the one with the highest count.

3
  • It's probably not the most efficient (based on CPU cycles), but it's definitely the first to mind as the least amount of code that gets the job done. +1.
    – Dean J
    Feb 18, 2010 at 20:01
  • you could skip the last step (running through the map entries and look for the highest count) if you kept a 'max' value as you incrmented the get(destingation)+1 step. If the new value was larger than any seen yet then store off a pointer to that entry. (I think this is the fastest solution as it is O(n). Certainly faster than sorting which is nLogn )
    – user244277
    Feb 18, 2010 at 20:10
  • My solution is O(N) - you're traversing the list of itineraries once, then you're traversing the list of destinations found once. Feb 18, 2010 at 20:12
0

If you don't mind using an external jar, you could use HashBag from apache commons to do this easily.

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);
    }
}

And then later you can call names.getCount("destination1") to get the number of occurrences of destination1

See http://commons.apache.org/collections/userguide.html#Bags

1
  • Thank you all for the extremely quick and helpful answers! I just started learning Java and although I haven't used HashBag before Ill be sure to look it up in the java API! Thank you again!
    – LeighA
    Feb 18, 2010 at 23:43
0

Try the group feature of the lambdaj library. To solve your problem you could group the Itenarary objects on the destination property and then find the group with the biggest size as in the following example:

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

In statistics, this is called the "mode". A vanilla Java 8 solution looks like this:

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λ is a library that supports mode() on streams. The following program:

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

(disclaimer: I work for the company behind jOOλ)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.