This problem doesn't require sorting all the given data. It will cause a huge overhead if n is close to 1, in which case the possible solution will run in a linear time O(n). Sorting increases time complexity to O(n*log n) (if you are not familiar with Big O notation, you might be interested in reading answers to this question). And for any n less than map size, partial sorting will be a better option.
If I understood you correctly, duplicated values need to be taken into account. For instance, for n=3 values 12,12,10,8,5 the third-largest value will be 10 (if you don't duplicate then the following solution can be simplified).
I suggest approaching this problem in the following steps:
- Reverse the given map. So that values of the source map will become the keys, and vice versa. In the case of duplicated values, the key (value in the reversed map) that comes first alphabetically will be preserved.
- Create a map of frequencies. So that the values of the source map will become the keys of the reversed map. Values will represent the number of occurrences for each value.
- Flatten the values of reversed map into a list.
- Perform a partial sorting by utilizing
PriorityQueue as container for n highest values. PriorityQueue is based on the so called min heap data structure. While instantiating PriorityQueue you either need to provide a Comparator or elements of the queue has to have a natural sorting order, i.e. implement interface Comparable (which is the case for Integer). Methods element() and peek() will retrieve the smallest element from the priority queue. And the queue will contain n largest values from the given map, its smallest element will be the n-th highest value of the map.
The implementation might look like this:
public static void printKeyForNthValue(Map<String, Integer> map, int n) {
if (n <= 0) {
System.out.println("required element can't be found");
}
Map<Integer, String> reversedMap = getReversedMap(map);
Map<Integer, Integer> valueToCount = getValueFrequencies(map);
List<Integer> flattenedValues = flattenFrequencyMap(valueToCount);
Queue<Integer> queue = new PriorityQueue<>();
for (int next: flattenedValues) {
if (queue.size() >= n) {
queue.remove();
}
queue.add(next);
}
if (queue.size() < n) {
System.out.println("required element wasn't found");
} else {
System.out.println("value:\t" + queue.element());
System.out.println("key:\t" + reversedMap.get(queue.element()));
}
}
private static Map<Integer, String> getReversedMap(Map<String, Integer> map) {
Map<Integer, String> reversedMap = new HashMap<>();
for (Map.Entry<String, Integer> entry: map.entrySet()) { // in case of duplicates the key the comes first alphabetically will be preserved
reversedMap.merge(entry.getValue(), entry.getKey(),
(s1, s2) -> s1.compareTo(s2) < 0 ? s1 : s2);
}
return reversedMap;
}
private static Map<Integer, Integer> getValueFrequencies(Map<String, Integer> map) {
Map<Integer, Integer> result = new HashMap<>();
for (Integer next: map.values()) {
result.merge(next, 1, Integer::sum); // the same as result.put(next, result.getOrDefault(next, 0) + 1);
}
return result;
}
private static List<Integer> flattenFrequencyMap(Map<Integer, Integer> valueToCount) {
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry: valueToCount.entrySet()) {
for (int i = 0; i < entry.getValue(); i++) {
result.add(entry.getKey());
}
}
return result;
}
Note, if you are not familiar with Java 8 method merge(), inside getReversedMap() you can replace it this with:
if (!reversedMap.containsKey(entry.getValue()) ||
entry.getKey().compareTo(reversedMap.get(entry.getValue())) < 0) {
reversedMap.put(entry.getValue(), entry.getKey());
}
main() - demo
public static void main(String[] args) {
Map<String, Integer> source =
Map.of("w", 10, "b", 12, "a", 10, "r", 12,
"k", 3, "l", 5, "y", 3, "t", 9);
printKeyForNthValue(source, 3);
}
Output (the third-greatest value from the set 12, 12, 10, 10, 9, 5, 3, 3)
value: 10
key: a
