时间戳

首页 > 解决方案 > 如何为 TreeMap 编写客户 equalsTo/compareTo/hasCode 以获取 Top N 值

java - 如何为 TreeMap 编写客户 equalsTo/compareTo/hasCode 以获取 Top N 值

问题描述

问题是：
客户想知道到目前为止哪些商品卖得最多。我们希望有效地将这些数据提供给我们的客户。
样本输入：
已售商品列表：
F|400
B|1000
A|500
A|600
C|1000
D|700
E|300
样本输出
A|1100
C|1000
B|1000
D|700

我的想法是在第一个 APIprocessInput()中，使用 item 和 value 的映射来跟踪到目前为止销售的所有项目，然后将更新的项目添加到最大优先级队列中。在第二个 APIprocessQuery()中，只需从队列中选择前 K 个。一个问题是processQuery，时间复杂度是O(NlogN)。

我们是否有可能TreeMap通过覆盖equalsTo, '来解决这个问题compareTo，hasCode以便树图按值排序。所以我们只是遍历 TreeMap 并返回 topN 项？

标签： javasortingtreemap

解决方案

您需要双向高效访问：当物品来时，您需要根据它们的名称（A、B、C）获取合计金额，但为了对它们进行排序，将使用合计金额。我认为您可以使用 aMap按名称查找项目，并使用 aSortedSet进行排序。由于数量本身不是唯一的（例如 B 和 C 在示例中都有 1000），因此排序也应该使用名称（因为它们是唯一的），这就是为什么一个集合足以满足该部分的原因：

import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;

public class Test {
    static class Item implements Comparable<Item> {
        final String name;
        int amount;
        Item(String name,int amount){
            this.name=name;
            this.amount=amount;
        }
        public int compareTo(Item o) {
            if(o.amount<amount)
                return -1;
            if(o.amount>amount)
                return 1;
            return o.name.compareTo(name);
        }
        public String toString() {
            return name+"|"+amount;
        }
    }
    
    Map<String,Item> itemmap=new HashMap<>();
    SortedSet<Item> sorted=new TreeSet<>();
    
    void add(String name,int amount) {
        Item i=itemmap.get(name);
        if(i!=null) {
            sorted.remove(i);
            i.amount+=amount;
        } else {
            i=new Item(name,amount);
        }
        itemmap.put(name,i);
        sorted.add(i);
    }
    public static void main(String[] args) {
        Test t=new Test();
        t.add("F",400);
        t.add("B",1000);
        t.add("xA",500);
        t.add("xA",600);
        t.add("C",1000);
        t.add("D",700);
        t.add("E",300);
        System.out.println("itemmap: "+t.itemmap);
        System.out.println("sorted: "+t.sorted);
    }
}

它产生输出（在 Ideone 上测试：https ://ideone.com/2d79aC ）

itemmap: {B=B|1000, C=C|1000, D=D|700, E=E|300, F=F|400, xA=xA|1100}
sorted: [xA|1100, C|1000, B|1000, D|700, F|400, E|300]

我故意重命名A为xA，否则地图将是A|1100, B|1000, C|1000，但这只是字母顺序的巧合（散列几个连续的单字母字符串并不会真正混合顺序）。C 和 B 以相反的顺序出现，因为这就是您所要求的。如果您希望它们作为 B，然后是 C，则交换compareTo()，或者只返回带有负号的当前值。

推荐阅读