0

If I have an ArrayList of these strings...

"String1, String1, String1, String2, String2, String2, String3, String3"

How can I find the most appearing string in this list? If there are any duplicates, I would want to put both into the same list and deal with that accordingly. How could I do this, assuming that the list of strings could be of any size.

This is about as far as I've gotten:

public String getVotedMap() {
        int[] votedMaps = new int[getAvailibleMaps().size()];


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

        int best = 0;

        for(int i = 0; i < votedMaps.length; i++) {
            if(best > i) {
                best = i;
            } else if(best == i) {

            } else {

            }
        }

    }

getAvailibleMaps() is a list of Maps that I would choose from (again, can get any size) Thanks!

6
  • 2
    Is this for a school assignment where you need to do it yourself or real-world code where you can use a library? Nov 13, 2014 at 1:06
  • 1
    @chrylis good question, since if you use Guava, you can use a Multiset to perform this feat
    – fge
    Nov 13, 2014 at 1:07
  • @chrylis i'm doing this for the sake of entertaining myself :D
    – loafy
    Nov 13, 2014 at 1:14
  • @Loafayyy Then wouldn't it be more entertaining to try to do it on your own instead of pasting a minimal attempt and asking others to do it for you?
    – Jason C
    Nov 13, 2014 at 1:15
  • @JasonC I'm just stuck right now and have been trying to figure it out for a while :/
    – loafy
    Nov 13, 2014 at 1:18

3 Answers 3

2

Use HashMap

The basic Idea is loading all the values into a hashtable. Hash tables are nice because you can assign a value to a unique key. As we add all the keys to the hashtable we are checking to see if it already exists. If it does then we increment the value inside.

After we have inserted all the elements into the hashtable then we go through the hashtable one by one and find the string with the largest value. This whole process is O(n)

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

for(int i = 0; i < array.length(); i++){
   if(map.get(array[i]) == null){
      map.put(array[i],1);
   }else{
      map.put(array[i], map.get(array[i]) + 1);
   }
}
int largest = 0;
String stringOfLargest;
for (Map.Entry<String, Object> entry : map.entrySet()) {
   String key = entry.getKey();
   int value = entry.getValue();
   if( value > largest){
      largest = value;
      stringOfLargest = key;
   }
}

if you want multiple largest strings then instead of just finding the largest and being done. You can add all the largest to a mutable list.

for example:

int largest = 0;
for (Map.Entry<String, Object> entry : map.entrySet()) {
   String key = entry.getKey();
   int value = entry.getValue();
   if( value > largest){
      largest = value;
   }
}
ArrayList<Object> arr = new ArrayList<Object>();
for (Map.Entry<String, Object> entry : map.entrySet()) {
   String key = entry.getKey();
   int value = entry.getValue();
   if( value == largest){
       arr.add(key);
   }
}

arr now stores all the most frequently appearing strings.

This process is still O(n)

5
  • Does this work when there are multiple strings that appear the same amount of time, when it adds both into a list for further processing?
    – loafy
    Nov 13, 2014 at 1:15
  • This answer would be more useful if you could explain good strategies for approaching this type of problem, as well as explain why you chose to do it the way you did it.
    – Jason C
    Nov 13, 2014 at 1:16
  • @Loafayyy When you tested it on that case, did it work?
    – Jason C
    Nov 13, 2014 at 1:16
  • @JasonC Yes, sortof... It only selects one of the highest string, whereas if there are two string appearing the same amount of times, it only chooses one.
    – loafy
    Nov 13, 2014 at 1:19
  • The last part I added should get all the largest strings
    – Jay
    Nov 13, 2014 at 1:25
0

Just iterate through the list and keep a HashMap<String,Integer> that counts how many times the string has appeared, eg.

Map<String,Integer> counts = new HashMap<String,Integer>();
for(String s : mostVoted) {
    if(counts.containsKey(s)) {
        counts.put(s,counts.get(s)+1);
    } else {
        counts.put(s,1);
    }
}
// get the biggest element from the list
Map.Entry<String,Integer> e = Collections.max(counts.entrySet(),new Comparator<Map.Entry<String,Integer>>() {

        @Override
        public int compare(Map.Entry<String,Integer> o1, Map.Entry<String,Integer> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }

});
System.out.printf("%s appeared most frequently, %d times%n",e.getKey(),e.getValue());
2
  • This answer would be more useful if you could explain good strategies for approaching this type of problem, as well as explain why you chose to do it the way you did it.
    – Jason C
    Nov 13, 2014 at 1:16
  • Yes, I get that part. I'm trying to find the one (or multiple) strings that appear the most. That's what I'm having a bit of trouble with.
    – loafy
    Nov 13, 2014 at 1:17
0

If you can use java 8, this will give you a list of most frequent strings or throw an exception if the list is empty.

List<String> winners = strings.stream()
        .collect(groupingBy(x->x, counting()))  // make a map of string to count
        .entrySet().stream()
        .collect(groupingBy(                    // make it into a sorted map
                Map.Entry::getValue,            // of count to list of strings
                TreeMap::new, 
                mapping(Map.Entry::getKey, toList()))
        ).lastEntry().getValue();

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.