Print the Key for the N-th highest Value in a HashMap-CodePudding

I have a HashMap and have to print the N-th highest value in the HashMap.

I have managed to get the highest value.

I have sorted the HashMap first so that if there are two keys with the same value, then I get the key that comes first alphabetically.

But I still don't know how to get the key for nth highest value?

public void(HashMap map, int n) {
    Map<String, Integer> sortedmap = new TreeMap<>(map);
    Map.Entry<String, Integer> maxEntry = null;
    for (Map.Entry<String, Integer> entry : sortedmap.entrySet()) {
        if (maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0) {
            maxEntry = entry;
        }
    }
    System.out.println(maxEntry.getKey());
}

CodePudding user response：

When finding the kth highest value, you should consider using a priority queue (aka a heap) or using quick select.

A heap can be constructed in O(n) time however if you initialize it and insert n elements, it will take O(nlogn) time. After which you can pop k elements in order to get the kth highest element

Quick select is an algorithm designed for finding the nth highest element in O(n) time

CodePudding user response：

Here is one way. It is presumed by Nth highest that duplicates must be ignored. Otherwise you would be asking about position in the map and not the intrinsic value as compared to others. For example, if the values are 8,8,8,7,7,5,5,3,2,1 then the 3rd highest value is 5 where the value 8 would be simply be value in the 3rd location of a descending sorted list.

initialize found to false and max to Integer.MAX_VALUE.
sort the list in reverse order
loop thru the list and continue checking if the current value is less than max. The key here is less than, That is what ignores the duplicates when iterating thru the list.
if the current value is less than max, assign to max and decrement n. Also assign the key
if n == 0, set found to true and break out of the loop.
if the loop finishes on its own, found will be false and no nth largest exists.

List<Entry<String,Integer>> save = new ArrayList<>(map.entrySet());
save.sort(Entry.comparingByValue(Comparator.reverseOrder()));

int max = Integer.MAX_VALUE;
boolean found = false;
String key = null;
for (Entry<String,Integer> e : save) {
    if (e.getValue() < max) {
        max = e.getValue();
        key = e.getKey();
        if (--n == 0) {
            found = true;
            break;
        }
    }
}

if (found) {
    System.out.println("Value = "   max);
    System.out.println("Key = "   key);
} else {
    System.out.println("Not found");
}

CodePudding user response：

This problem doesn't require sorting all the given data. It will cause a huge overhead if n is close 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