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!

Improve this question
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? Commented Nov 13, 2014 at 1:06
  • 1
    @chrylis good question, since if you use Guava, you can use a Multiset to perform this feat Commented Nov 13, 2014 at 1:07
  • @chrylis i'm doing this for the sake of entertaining myself :D Commented 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? Commented Nov 13, 2014 at 1:15
  • @JasonC I'm just stuck right now and have been trying to figure it out for a while :/ Commented Nov 13, 2014 at 1:18

3 Answers 3

Reset to default
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)

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

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?
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.
@Loafayyy When you tested it on that case, did it work?
@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.
The last part I added should get all the largest strings
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());
Improve this answer

2 Comments

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.
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.
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();
Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.