打印 HashMap 中第 N 个最高值的键

Question

我有一个 HashMap 并且必须在 HashMap 中打印第 N 个最高值。

我获得了最高的价值。

我先对 HashMap 进行了排序，这样如果有两个键具有相同的值，然后我得到第一个 alphabetically.

的密钥

但是我还是不知道如何获取第n个最高值的key？

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());
}

Answer 1

这个问题不需要对所有给定数据进行排序。如果 n 接近 1 会导致巨大的开销，在这种情况下可能的解决方案将运行在线性时间 O(n).排序将时间复杂度增加到 O(n*log n)（如果您不熟悉 Big O 表示法，您可能有兴趣阅读answers to this question）。对于小于地图大小的任何 n，部分排序将是更好的选择。

如果我没有理解错的话，需要考虑重复值。例如，对于 n=3 值 12,12,10,8,5，third-largest 值将是 10（如果您不复制，则可以简化以下解决方案).

我建议按照以下步骤解决这个问题：

反转给定的地图。这样源映射的值将成为键，反之亦然。在重复值的情况下，按字母顺序首先出现的键（反向映射中的值）将被保留。
创建一个频率图。这样source map的values就会成为reversed map的keys。值将代表每个值的出现次数。
将反转映射的值展平。
利用PriorityQueue as container for n highest values. PriorityQueue is based on the so called min heap data structure执行部分排序。在实例化 PriorityQueue 时，您要么需要提供 Comparator，要么队列的元素必须具有自然排序顺序，即实现接口 Comparable（Integer 就是这种情况） ).方法 element() 和 peek() 将从优先级队列中检索最小的元素。并且队列将包含给定映射中的 n 个最大值，其最小元素将是映射的第 n 个最大值。

实现可能如下所示：

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;
}

注意，如果您不熟悉Java 8 方法merge()，在getReversedMap() 中您可以将其替换为：

if (!reversedMap.containsKey(entry.getValue()) || 
      entry.getKey().compareTo(reversedMap.get(entry.getValue())) < 0) {
   reversedMap.put(entry.getValue(), entry.getKey());
}

main() - 演示

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);
}

输出（集合中的third-greatest值 12, 12, 10, 10, 9, 5, 3, 3）

value:  10
key:    a

Answer 2

这是一种方法。 Nth 推定必须忽略重复项。否则，您会询问地图中的位置，而不是与其他地图相比的内在价值。例如，如果值为 8,8,8,7,7,5,5,3,2,1，则 3rd 最高值为 5，其中值 8 将只是 3rd 位置的值降序排序列表。

将found初始化为false，将max初始化为Integer.MAX_VALUE。
根据值对列表进行倒序排序。由于 TreeMap 已经按键排序并且是 stable sort（请参阅 Sorting algorithms），键将保留重复值的排序顺序。
遍历列表并继续检查当前值是否小于最大值。这里的关键是 less than，这就是在遍历列表时忽略重复项的原因。
如果当前值小于max，赋值给max，自减n。同时分配密钥
如果 n == 0，将 found 设置为 true 并跳出循环。
如果循环自行完成，则 found 将为假，并且 nth 最大的不存在。

Map<String, Integer> map = new TreeMap<>(Map.of(
         "peter" , 40, "mike" , 90, "sam",60, "john",90, "jimmy" , 32, "Alex",60,"joan", 20, "alice", 40));

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");
}

打印

Value = 60
Key = Alex

Answer 3

当找到第 k 个最高值时，您应该考虑使用优先级队列（又名堆）或使用快速 select。

堆可以在O(n) 时间内构造，但是如果您初始化它并插入n 个元素，则需要O(nlogn) 时间。之后你可以弹出 k 个元素以获得第 k 个最高元素

Quick select 是一种设计用于在 O(n) 时间内找到第 n 个最高元素的算法

打印 HashMap 中第 N 个最高值的键

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

java

algorithm

sorting

hashmap