Java Algo to Find smallest and second smallest Number in List

Question

Hi,

I need to find smallest and second smallest number in a list.

Can I do this using single loop? Also, we need to consider the case of two multiple occurences of a number.

Ex: 1. from list [20,30,90,50] output 20 ,30 2. from list [30,30,90,50] output 30 ,30

plz help

Answer 1

I want to encourage you to do your homework on your own and understand the concepts behind it, so I won't post any code for you, but here are some things to guide you:

• It is possible to do this with only one loop.
• Make one pass through the list, all the time saving the current smallest and second-smallest number. These are the smallest and second-smallest up until this point in the list.
• At the end, you'll notice (if you've done it correctly) that you have the smallest and second-smallest numbers.
• In the case of a duplicate number, just be sure to include an equals check in the condition you use; i.e., you'll be checking for smaller values, so use i <= smallest and i <= secondSmallest as your two conditions (as opposed to a strict smaller than comparison).

Answer 2

Call Collections.min(), then remove the element you got from the List, and call it again?

    List<Integer> list = Arrays.asList(20, 30, 90, 50);
    List<Integer> copy = new ArrayList<Integer>(list);
    Integer smallest = Collections.min(copy); // 20
    copy.remove(smallest);
    Integer secondSmallest = Collections.min(copy); // 30

(Making a copy not to mess with the original.)

This is probably far from the most performant solution (From Collections.min() Javadoc: "This method iterates over the entire collection, hence it requires time proportional to the size of the collection."), but it's very simple to write and maintain. :)

Answer 3

Arrays.sort() or Collections.sort() and the take two smallest elements.

Answer 4

I am sorry, Actually I dont have list of Integers. But I ahve list of objects.

Anyways, thanks for the help. I hope the following code works

if (minimum==0 || obj.getValue() < minimum) {
    second = minimum;
    minimum= obj.getValue();
} else if (obj.getValue() < second || second==0) {
    second = obj.getValue();
}

Answer 5

Pseudocode only since it's homework, to be turned into your language of choice. Assuming the list has two or more numbers in it (indexes 0 and 1):

set lowest to value at index 0.
set second_lowest to value at index 1.
if lowest is greater than second_lowest:
    swap lowest and second_lowest.
vary idx from 3 to last element:
    if value at index idx is less than lowest:
        set second_lowest to lowest
        set lowest to value at index idx
    else
        if value at index idx is less than second_lowest:
            set second_lowest to value at index idx

This works by basically checking every number to see if it should be the new lowest or new second lowest number. It can be done in one loop.

What you want to do is to run this program in your head, writing down on paper what the variables get changed to. That's a good way to understand how a computer works. Consider the list [30,20,90,10,50,12,7], following the following steps:

lowest   second   description
------   ------   -----------
    30       20   store first two elements.
    20       30   swap them if in wrong order (they are).
    20       30   90 is not less than either so ignore.
    10       20   10 is less than lowest (20) so move
                  lowest to second, store 10 to lowest.
    10       20   50 is not less than either so ignore.
    10       12   12 is less than second (20) so
                  store 12 to second.
     7       10   7 is less than lowest (10) so move
                  lowest to second, store 7 to lowest.