如何在地图中打印出最大的数字

Question

我正在阅读有关Java中的地图的内容。我想遍历一个包含不同数字的地图，并打印出地图中最大的3个数字。这是我的代码：

public class Test {

    private static int number=0;

    public static void main(String[] args) {

        Map<String,Integer> m = new HashMap<String,Integer>();

        m.put("haha", 1);
        m.put("aa", 2);
        m.put("rewq", 3);
        m.put("la", 12);
        m.put("oia", 10);
        m.put("uyta", 4);
        m.put("jpa", 5);


        for (Entry<String, Integer> e : m.entrySet()) {

            if (e.getValue() > number) {
                number = e.getValue();
            }

        }
        m.values().remove(number);
        System.out.println(number);

        for (Entry<String, Integer> e : m.entrySet()) {

            if (e.getValue() > number) {
                number = e.getValue();
            }

        }
        m.values().remove(number);
        System.out.println(number);


        for (Entry<String, Integer> e : m.entrySet()) {

            if (e.getValue() > number) {
                number = e.getValue();
            }

        }
        m.values().remove(number);
        System.out.println(number);

    }

}

输出结果为

12
12
12

我该如何更改代码使其输出如下所示：

12
10
5

谢谢

- Joe

---

m.values().stream().sorted(Comparator.reverseOrder()).limit(3).forEach(System.out::println);仅适用于Java 8。 - Dominik Sandjaja

如果你使用for循环来搜索/删除/打印3次，而不是复制代码，那么你会让自己的生活更轻松。 - Andy Turner

@DominikSandjaja 但这需要O(n)的内存和O(n log n)的排序时间。top n应该只需要n（在这种情况下为3）的内存和线性时间。 - David Ehrmann

@DavidEhrmann，你肯定需要O(n)的内存来存储前n个项目吧？ - Andy Turner

经典的“算法”解决方案是使用O(n) 选择算法来查找第三大的数字，然后再次扫描值，保留每个大于或等于第三大的元素。当存在重复时会有些混乱，但基本思路相同。 - David Ehrmann

Answer 1

你的代码问题在于，你在没有重置最大找到的数字的情况下，使用相同的条件三次迭代同样的数字。你的代码基本上查找最大数字，然后比较地图中每个项目是否有更大的数字两次。当然，这什么都没找到并输出之前找到的最大数字。

你真正想要的是:

• 获取所有值（而不是条目集）
• 对值进行排序
• 打印出前三个

在Java中，可以这样做:

ArrayList<Integer> values = new ArrayList<Integer>(m.values());
Collections.sort(values);
// turn ascending to descending
Collections.reverse(values);
System.out.println(String.format("%d, %d, %d", values.get(0), values.get(1), values.get(2)));

即使只需要前三个值，排序所有值也会带来一些计算开销，但对于少于数千条的列表来说，这是可以忽略的。

- Hubert Grzeskowiak

Answer 2

目前你只有一个变量来存储最大值，因此在程序结束时，你总是会打印出最大值，因为你还在将其与最大值进行比较。这就是为什么每次都得到相同的值。你可以将所有数字读入一个arraylist中，然后调用collections.sort方法，并从中取出前三个并打印出来。

使用你目前的代码，你也可以做以下操作

for(int i = 0; i < 3; i++)
{
    //this makes sure you aren't comparing the same largest number everytime
    number = Integer.MIN_VALUE;
    for (Entry<String, Integer> e : m.entrySet()) {
        if (e.getValue() > number) {
            number = e.getValue();
        }
    }
    m.values().remove(number);
    System.out.println(number);
}

- RAZ_Muh_Taz

---

目前你只有一个变量来存储最大值，因此在程序结束时总是会打印出最大值。看起来你忽略了 OP 尝试在查找下一个最大值之前删除先前选择的最大数的问题。因此，你还应该解释一下这种方法为什么行不通。 - Tom

Answer 3

您也可以使用Java 8的功能来实现您想要的内容。

        Map<String,Integer> m = new HashMap<String,Integer>();

        m.put("haha", 1);
        m.put("aa", 2);
        m.put("rewq", 3);
        m.put("la", 12);
        m.put("oia", 10);
        m.put("uyta", 4);
        m.put("jpa", 5);


        m.values()
            .stream()
            .sorted(Comparator.reverseOrder())
            .limit(3)
            .forEach(System.out::println);

- iamorozov