按两个条件排序

长图

我有一个包含字段的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();
                }
            }
        }

Xiangpeng

您可以使用优先级队列结构。https://docs.oracle.com/javase/10/docs/api/java/util/PriorityQueue.html

对于每个ID，制作一个地图ID -> [大小为m的优先队列]，大小为m的意思是poll当已经有m个价格时，每次添加一个价格。

那么每个 ID最多有m 个价格，拿这张地图并建立另一个 [大小为k 的优先队列] 你将解决问题。

复杂度为 O(n*log(k))

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。