java - 按两个条件排序

Question

我有一个包含字段的 n 对象数组:ID、价格。相同的 ID 可能在一个数组中出现多次。我想为每个 ID 找到最便宜的 k 且不超过 m 对象。

同时，k <= n, m <= k。

喜欢:

n = 1,000,000
k = 10,000
m = 50

class Issue {
    int ID;
    int price;

    public Issue(int ID, int price) {
        this.ID = ID;
        this.price = price;
    }
}
Issue[] arr = {
    new Issue(1, 100),
    new Issue(1, 150),
    new Issue(1, 200),

    new Issue(2, 1),
    new Issue(2, 2),
    new Issue(2, 3),

    new Issue(3, 4),
    new Issue(3, 5),
    new Issue(3, 30),
    new Issue(3, 6),

    new Issue(4, 7),
    new Issue(4, 8),
    new Issue(4, 9),
    new Issue(4, 10),
};

如果:

n = 14
k = 5
m = 2

决定如:

new Issue(2, 1),
new Issue(2, 2),
new Issue(3, 4),
new Issue(3, 5),
new Issue(4, 7),

我使用 java 流解决了这个问题，但是使用了几种类型，O 的结果很糟糕。您建议使用什么算法来解决？

@Xiangpeng 感谢您的回答。你是认真的吗？

        int k = 5; // only k cheapest from array n
        int m = 2; //max same iDs
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        stream(arr).forEach(product -> {
            if (!map.containsKey(product.ID)) {
                PriorityQueue<Integer> integers = new PriorityQueue<>(reverseOrder());
                integers.add(product.price);
                map.put(product.ID, integers);
            } else {
                PriorityQueue<Integer> integers = map.get(product.ID);
                integers.add(product.price);
                map.put(product.ID, integers);
                if (integers.size() > m) {
                    integers.poll();
                }
            }
        });
        PriorityQueue<Integer> priorityQueueK = new PriorityQueue<>(k, reverseOrder());
        for (PriorityQueue<Integer> values : map.values()) {
            for (int i = 0; i < values.size(); ) {
                priorityQueueK.add(values.poll());
                if (priorityQueueK.size() > k) {
                    priorityQueueK.poll();
                }
            }
        }

Answer 1

您需要一个具有两个条件的比较器。

Comparator.comparing((Issue a) -> a.ID ) 通过 ID 创建一个新的比较器

thenComparing 添加第二个条件，在本例中比较价格

list.sort(Comparator.comparing((Issue a)-> a.ID ).thenComparing((a,b)-> Integer.compare(a.price, b.price) ));

我建议使用 getters 和 setters 方法

list.sort(Comparator.comparing((Issue a)-> a.getId() ).thenComparing((a,b)-> Integer.compare(a.getPrice(), b.getPrice()) ));