CODEWITHSUNDEEP
javaalgorithmsortingsearch
LongMap
LongMap

Reputation: 3

Sort by two conditions

I have an array of n objects with fields: ID, price. Identical IDs may occur more than once in an array. I want to find the cheapest k and no more than m objects for each IDs.

At the same time, k <= n, m <= k.

Like:

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),
};

If: 

n = 14
k = 5
m = 2

decision like:

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

I solved this problem using java streams, but using several sorts and O comes out bad. What would you suggest an algorithm to solve?

@Xiangpeng thanks for the answer. Do you mean it?

        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();
                }
            }
        }

Upvotes: 0

Views: 541

Answers (3)

Xiangpeng
Xiangpeng

Reputation: 44

You can use the priority queue structure. https://docs.oracle.com/javase/10/docs/api/java/util/PriorityQueue.html

For each ID, make a map ID -> [ priority queue of size m], size m means do a poll each time you add a price when there are already m prices.

There are then at most m prices for each ID, take this map and build another [ priority queue of size k ] you will solve the problem.

Complexity is O(n*log(k))

Upvotes: 0

imperezivan
imperezivan

Reputation: 781

You need a comparator with two conditions.

Comparator.comparing((Issue a) -> a.ID ) create a new comparator by ID

thenComparing add a second condition, in this case compare price

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

i suggest use getters and setters methods

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

Upvotes: 1

ruakh
ruakh

Reputation: 183321

The simplest approach is to sort the issues by price, then iterate over them, keeping track of how many issues you've already selected with a given ID (so that you can skip any issues over the limit). Once you've selected the right number of issues, abort.

So:

Collections.sort(arr, (issueA, issueB) => Integer.compare(issueA.price, issueB.price));

final List<Issue> result = new ArrayList<>();
final Map<Integer, Integer> countsByID = new HashMap<>();

for (final Issue issue : arr) {
    if (! countsByID.containsKey(issue.ID)) {
        countsByID.put(issue.ID, 0);
    }

    if (countsByID.get(issue.ID) >= m) {
        continue;
    }

    result.add(issue);

    countsByID.put(issue.ID, countsByID.get(issue.ID) + 1);

    if (result.size() == k) {
        return result;
    }
}

return result; // couldn't find k values satisfying the restrictions

Upvotes: 0

Related Questions