Most efficient way to order an array of Strings by frequency

Question

I have an array of Strings:

String[] stringArray = {"x", "y", "z", "x", "x", "y", "a"};

What is the quickest/most efficient way to order this into a smaller Collection in order of how frequent each String is with its frequency?

I though about using the String as a key in a HashMap<String,Integer> but this wouldnt be sorted in terms of frequency

My other method i considered is using a TreeMap<Integer, String[]> with a list of Strings with that integer, but there seems a lot of checking involved..

Im trying to avoid using more than one loop If possible as my String arrays will be much larger than the one above. Thanks!

EDIT What i want is just to be able to output the Strings in order of frequency and preferably be able to pair that String with its frequency in the array, So for example two output arrays:

["x", "y", "z", "a"]
[3,2,1,1]

This would be quite a simple problem if speed wasnt an issue which is why i ask the great minds on here :)

Answer 1

You can solve this in two steps:

1. Create a counter object - a Map<String, Integer> listing for each string the number of times it appears in the input: in other words, it's a frequency map. This is O(n), as you only need to traverse the input once for building the map

2. With the previous map, create a list with its keys, sorted using the frequency of items (the values in the map) as ordering criteria. This is O(n log n), and you can call Collections.sort(), with a Comparator that uses the string frequency for the comparisons

This is what I mean:

String[] stringArray = {"x", "y", "z", "x", "x", "y", "a"};

final Map<String, Integer> counter = new HashMap<String, Integer>();
for (String str : stringArray)
    counter.put(str, 1 + (counter.containsKey(str) ? counter.get(str) : 0));

List<String> list = new ArrayList<String>(counter.keySet());
Collections.sort(list, new Comparator<String>() {
    @Override
    public int compare(String x, String y) {
        return counter.get(y) - counter.get(x);
    }
});

After the above code executes, the variable list will contain the following values (the order between elements of the same frequency is unspecified):

[x, y, a, z]

It's trivial to convert the list to an array:

list.toArray(new String[list.size()])

And if you need to find out the frequency of each string, just iterate over the sorted keys:

for (String str : list) {
    int frequency = counter.get(str);
    System.out.print(str + ":" + frequency + ", ");
}