You can solve this in two steps:
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 isO(n)
, as you only need to traverse the input once for building the mapWith 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 callCollections.sort()
, with aComparator
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 + ", ");
}