CODEWITHSUNDEEP
javacollectionshashmapmaxcycle
Felix
Felix

Reputation: 1

How to get the top M values from a Map?

So I am writing this program, which calculates different things about the Collatz-conjucture. So basically for a number I calculate a cycle and its length, like this:

For 8: [8, 4, 2, 1] Length: 4

Now I want to calculate until 1000.

And for every number the length of the cycle is different.

So for example the length of the cycle for number 43 can be bigger than that for 45.

And I want to get the biggest lengths in ascending order.

Like this:
Number    1 2 3 6 7 9 1825 27 54 73 97 129 171 231 313 327 649 703 871
Length(N) 0 1 7 8 16 19 20 23 111 112 115 118 121 124 127 130 143 144 170 178

I put the numbers in HashMap with the numbers as keys and the lengths as values.

Now I have no clue how to get the biggest lengths in ascending order.

Is there a function that helps me with that? Do I have to use a loop and more lists?

The Collections.Max is of no help, because it gets only one value, but I need more than one.

Upvotes: 0

Views: 84

Answers (2)

cellepo
cellepo

Reputation: 4499

This amounts to essentially sorting a list composed of the map's values.

Returns the top m values of your Map, ascending:

public static List<Integer> topMValuesAscending(Map<?, Integer> map, int m){
  final List<Integer> values = new ArrayList<Integer>(map.values());
  Collections.sort(values);
  final int valuesCount = values.size();

  return values.subList(valuesCount - m, valuesCount);
}

I believe this is optimal, and is O[s*Log(s)] log-linear, where s is the size of the map.

Upvotes: 0

Alad Mocu
Alad Mocu

Reputation: 46

You should use any sorting algorithm, (like merge) and then pick the amount you'd like to get from the sorted map.

Upvotes: 2

Related Questions