Retrieve the two highest item from a list containi

Question

How can retrieve the two highest item from a list containing 100,000 integers without having to sort the entire list first?

Answer 1

Iterating through the entire list is the only way to do it without sorting.

Answer 2

The best time you can expect is linear, since you have to at least look through all the elements.

Here is my pseudocode to solve the problem:

//assume list has at least 2 elements
(max, nextMax) = if (list[0] > list[1])
                 then (list[0], list[1])
                 else (list[1], list[0])

for (2 <= i < length) {
    (max, nextMax) = if       (max < list[i])     => (list[i], max)
                     elseif   (nextMax < list[i]) => (max, list[i])
                     else     (no change)         => (max, nextMax)
}

return (max, nextMax)

Answer 3

Copy your List to List_copy. Retrieve the highest value and get its position by:

Highest_value = max(List_copy)
Highest_position = List_copy.index(max(List_copy))

Assign 0 to the Highest_value.

List_copy[Highest_position] = 0

And run your line again.

Second_Highest = max(List_copy)

Answer 4

Another solution that uses only base Python functions can be seen below:

>>> largest = max(lst)
>>> maxIndex = lst.index(largest)
>>> secondLargest = max(max(lst[:maxIndex]), max(lst[maxIndex+1:]))

If we split a list around its largest number, we know that the second largest number is either in the left half or the right half. So, we can trivially find the second largest number by simply finding the larger of the largest number in the left and right half of the list.

It's trivial to show this is O(n) time and O(1) space. We traverse the list once to find the largest element, then again to find the second largest. We only store the largest values themselves and the index of the largest value.

Answer 5

Sort the list, and if list is not null, extract last two element

>>> a=[0,6,8,5,10,5]
>>> a.sort()
>>> a
[0, 5, 5, 6, 8, 10]
>>> if a:
...  print a[-1],a[-2]
... 
10 8

Simple and most efficient:)

Now if sorting is not required, find max, remove max, find max again

>>> a=[0,6,8,5,10,5]
>>> max(a)
10
>>> a.remove(max(a))
>>> max(a)
8
>>> 

Of course, you will lose the original list but you can create a temporary list as well.

Answer 6

In Python, use heapq.nlargest. This is the most flexible approach in case you ever want to handle more than just the top two elements.

Here's an example.

>>> import heapq
>>> import random
>>> x = range(100000)
>>> random.shuffle(x)
>>> heapq.nlargest(2, x)
[99999, 99998]

Documentation: http://docs.python.org/library/heapq.html#heapq.nlargest