Use the least number of comparisons to get the largest and 2nd largest number in the given integer array. Return the largest number and 2nd largest number.
Assumptions
The given array is not null and has length of at least 2
Examples
{2, 1, 5, 4, 3}, the largest number is 5 and 2nd largest number is 4.
Solution: single elimination
Key Insight:
Loser of each match must be kept in case of largest and second largest matching up early.
After each match, keep the winner as well as the loser in the form of an object
public class Solution {
class Element {
List<Integer> losers;
Integer value;
Element(int value, List<Integer> losers){
this.value = value;
this.losers = losers;
}
}
public int[] largestAndSecond(int[] array) {
//pre process
Queue<Element> q = new LinkedList<>();
int i = 0;
int j = 1;
while (j < array.length){
int one = array[i];
int two = array[j];
List<Integer> losers = new ArrayList<>();
if (one >= two){
losers.add(two);
q.offer(new Element(one, losers));
} else {
losers.add(one);
q.offer(new Element(two, losers));
}
i += 2;
j += 2;
}
if (i < array.length){
q.offer(new Element(array[i], new ArrayList<Integer>()));
}
while(q.size() > 1){
Element one = q.poll();
Element two = q.poll();
if (one.value >= two.value){
one.losers.add(two.value);
q.offer(one);
} else {
two.losers.add(one.value);
q.offer(two);
}
}
Element winner = q.poll();
int max = Integer.MIN_VALUE;
Integer value = winner.value;
List<Integer> losers = winner.losers;//additional space
for (int k = 0; k < losers.size();k++){
max = Math.max(max, losers.get(k));
}
return new int[]{value, max};
}
}