How to only return ArrayList of strings with minimum number of occurrences?

Question

I have a String[], originalStringArray, that has duplicates in them. So {"dog","cat","dog","fish","dog","cat"}.

I wanted to make a function that only returns the strings that occur exactly a certain number of times. For here, if I said 3, it would return "dog" but not "cat".

Here's my current code:

public ArrayList<String>  returnMultiples(String[] originalStringArray,int requiredCount){
    ArrayList<Integer> mCount = new ArrayList<>();
    List<String> list = Arrays.asList(originalStringArray);
    ArrayList<String> result = new ArrayList<>();

    // Count occurrences in original string
    for(String item: originalStringArray){
        mCount.add(Collections.frequency(list,item));
    }

    // If frequency is equal to count, add to array list
    for(int i=0; i<mCount.size(); i++){
        if(mCount.get(i) == requiredCount){
            result.add(originalStringArray[i]);
        }
    }

    return result;
}

The problem I have is, I read somewhere that the Collections library is very slow and drag, and it also seems like that this method could be reduced using HashSets and tables. Unfortunately, I'm kind of at a loss on how to do that. Is there a better way to do this?

Answer 1

Some sort of map will be required to carry this out. Here is an example written using HashMaps:

public ArrayList<String> returnMultiples(String[] array, int min){
    HashMap<String, Integer> counts = new HashMap<String, Integer>();//instantiate a new HashMap

    //loop through the array and count the occurrences of each different string in the array
    for(int i = 0; i < array.length; i++){
        String word = array[i];
        if(counts.containsKey(word))
            counts.put(word, counts.get(word) + 1);
        else
            counts.put(word, 1);
    }

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

    //check if any of the words occur >= min times. if so, add them to the returning list.
    for(String key : counts.keySet()){
        if(counts.get(key) >= min){
            multiples.add(key);
        }
    }

    return multiples;//return the list we just created of the desired strings
}

Depending on the length of the strings, the HashMap will be a little more efficient than using collections although the difference is mostly negligible.

Answer 2

You will have to use HashMap for this task.

Lets say your HashMap will contain count of occurences of given string, so it will be of type HasMap<String,Integer>

And now, lets iterate over your collection:

1. Get another string from your collection
2. Check if give string exists in HashMap (#contains)
3. If not exist, put new element with String key (hashMap.put(stringKey,1);
4. If it exists, put element with the same key, but increment the internal counter (hashMap.put(stringKey,hashMap.get(stringKey)+1)
5. Continue

Now you have hashmap contains exact number of occurences of given strings from your collections.

Fast lookup would be to create reverse HashMap<Integer,String> but there is a possibility that counts will duplicate and this wont work. To get the String that occurences matches the given string you will have to iterate over all keys of map, and return only those that occurences count matches your criteria.