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

Question

我有一个hashmap，必须在hashmap中打印n - 最高值。

我设法获得了最高的 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());
}

Answer 1

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

• 初始化<代码>找到 false 和max to integer.max_value。
• 根据价值以相反顺序对列表进行排序。由于treemap已经通过键进行排序，并且是stable Sort（请参阅分类算法）钥匙将保持序列的顺序值。
• 通过列表进行循环，然后继续检查当前值是否小于最大值。这里的关键是小于，这就是忽略通过列表迭代时的重复项。
• 如果当前值小于最大值，请分配给max和减少n。还要分配键
• ，如果n == 0，set true 并突破循环。
• 如果循环单独完成，则发现最大的 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 2

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

如果我理解正确，则需要考虑重复的值。例如，对于 n=3 值 12,12,10,8,5，第三大值将为 10（如果您不重复，则可以简化以下解决方案）。

我建议通过以下步骤解决此问题：

• 反转给定的地图。这样源映射的值将成为键，反之亦然。如果存在重复值，则将保留按字母顺序排列在前的键（反向映射中的值）。
• 创建频率图。这样源映射的值将成为反转映射的键。值将表示每个值出现的次数。
• 将反转映射的值压平到列表中。
• 利用 PriorityQueue 作为 n 最高值的容器。 PriorityQueue 基于所谓的最小堆数据结构。在实例化 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() - 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 （集合中的第三大值 12, 12, 10, 10 , 9, 5, 3, 3)

value:  10
key:    a

Answer 3

当找到第 k 个最高值时，您应该考虑使用优先级队列（也称为堆）或使用快速选择。

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

快速选择是一种算法，旨在在 O(n) 时间内查找第 n 个最高元素