Save top N results to fixed array - sequentially

Question

I have a huge list of numbers and I'm doing some calculations over each record, e.g:

123 456 789 213 546 789 78 156 489 952 456 789 ......

and after proccessing the list I'm getting the results sequentially (they are not stored in any structure), e.g.

0.156 0.895 0.12 0.145 0.146 0.222 0.123 0.489 ........

Is there some practice, how to save for example top 5 results to fixed array?

1st step:

[0.156]

2nd step:

[0.895 0.156]

5th step:

[0.895 0.156 0.146 0.145 0.12]

nth step:

[0.895 0.489 0.222 0.156 0.146]

It should have complexity O(n), because there is no sorting.

possible duplicate of [Getting Top Four Maximum value from Java Array](http://stackoverflow.com/questions/14122526/getting-top-four-maximum-value-from-java-array) — BobTheBuilder, Apr 11 '13 at 08:24

score 1 · Answer 1 · answered Apr 11 '13 at 08:20

Basically it is pretty easy you have a 5 element array say

[88, 77, 66, 55, 44]

for each new number search through the array and insert in the approriate possition if there is one (a basic for / while loop can be used).

i.e. if you get 60 the array would become

[88, 77, 66, 60, 55]

There are issues like at the start before you get 5 element. Since this is an exercise I will leave you to write the code

Vincent van der Weele · Accepted Answer · 2013-04-11T08:28:45.247

1

If you use a LinkedList and only insert in the first 5 elements, I think this would work.

public List<Double> getTop(List<Double> inputs) {
    List<Double> top = new LinkedList<>();
    for (Double input : inputs) {
        int i = 0;
        while (i < 5 && i < top.size() && input < top.get(i))
            i++;
        if (i < 5)
            top.add(i, input);
    }
    return top.subList(0, 5);
}

edited Apr 11 '13 at 08:28

answered Apr 11 '13 at 08:22

Vincent van der Weele

12,927
1
33
61

score 0 · Answer 3 · edited May 23 '17 at 11:49

0

In case of only 5 elements, iterating over the array and saving max 5 elements is not so hard.

You can take a look at this, that and here for a more comprehensive answers.

edited May 23 '17 at 11:49

Community

1
1

answered Apr 11 '13 at 08:20

BobTheBuilder

18,858
6
40
61

Save top N results to fixed array - sequentially

3 Answers3