Java: grabbing second highest

Question

Possible Duplicate:
Finding the second highest number in array

I have this,

       for(int i=0;i<Dices.length;i++){
        if( Dices[i].getValue() > highest ){
            highest = Dices[i].getValue();
        }
       }

to get highest value. I now want to get the second highest, how can I do it? Cant i take advantage of this highest variable for getting the second highest?

You have a defined value for highest? Why don't you then have a defined value for second highest? Put them in a ArrayList sort them ascending, loop through them and store previous value. — Fredrik, May 25 '11 at 16:25

score 5 · Accepted Answer · answered May 25 '11 at 16:30

5

How about something like this in O(n) speed:

// first, second, d0, d1, di all typed by whatever getValue() returns...
// This assumes you have at least two elements in your Dices array

d0 = Dices[0].getValue();
d1 = Dices[1].getValue();
if (d0 > d1) {
    first=d0;
    second=d1;
} else {
    first=d1;
    second=d0;
}

for (int i = 2; i < Dices.length; i++) {
    di = Dices[i].getValue();
    if (di > first) {
        second = first;
        first = di;
    } else if (di > second)
        second = di;
}

answered May 25 '11 at 16:30

Andy

5,108
3
26
37

1

@Andy great solution! This is exactly the thing I was considering when I commented on @Sean's answer. – Ryan Castillo May 25 '11 at 16:41
@Andy, +1 for implementing the correct solution – mre May 25 '11 at 16:44
1

+1 for efficiency, although you could say that this is a classic case of premature optimization. Now please let's have the 3 largest values :-) – Sean Patrick Floyd May 25 '11 at 16:46
@Sean I'm to lazy to spit out an answer for the top three values. I'd use your solution for that, unless I really needed speed. – Andy May 25 '11 at 16:49
@Andy I wasn't seriously asking for one, I just pointed out the weakness of your answer. But given an array with more than a million entries, I'd also use your answer. – Sean Patrick Floyd May 25 '11 at 16:52

score 2 · Answer 2 · answered May 25 '11 at 16:22

2

Sort the array using a custom Comparator (make a copy of the array if you can't sort the original)

Pick the last-but-one item of the sorted array:

// hopefully you have checked in advance that there is more than one item
return sortedDices[sortedDices.length-2];

answered May 25 '11 at 16:22

Sean Patrick Floyd

292,901
67
465
588

Since we're just talking about the two highest do you necessarily have to sort the entire array? I'm just trying to think of logic where you traverse the array only once. I do agree that sorting the array is the best solution just trying to think outside of the box here. – Ryan Castillo May 25 '11 at 16:33
@Ryan which is the best depends on the situation. Mine is the most usable and manageable, Andy's is the most efficient (at least for large arrays) – Sean Patrick Floyd May 25 '11 at 17:01

Java: grabbing second highest

2 Answers2