2

So I have to find the second largest number from list. I am doing it through simple loops.

My approach is to divide a list into two parts and then find the largest number into two parts and then compare two numbers. I will choose the smaller number from two of them. I can not use ready functions or different approaches.

Basically, this is my code. But it does not run correctly

#!/usr/local/bin/python2.7

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
largest=alist[0]
h=len(alist)/2 
m=len(alist)-h

print(alist)

for i in alist:
    if alist[h]>largest:
      largest=alist[h]
      i=i+1
print(largest)
martineau
  • 119,623
  • 25
  • 170
  • 301
Manu Lakaster
  • 4,659
  • 4
  • 15
  • 10
  • 4
    What if both are in the same part of the list? – Ignacio Vazquez-Abrams Oct 31 '13 at 02:40
  • 1
    Here is the answer for your problem! http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on – andilabs Oct 31 '13 at 02:41
  • 1
    What if the largest and the second largest number are in the same side of your divide? `[-10, -5, 10, 20]` for example? Your method will not capture `-5` rather than the desired `10`. Consider using a list (or [deque](http://docs.python.org/2/library/collections.html#collections.deque)) of length 2 to store the two highest encountered numbers. – Josha Inglis Oct 31 '13 at 02:46

14 Answers14

11

O(n^2) algorithm:

In [79]: alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]

In [80]: max(n for n in alist if n!=max(alist))
Out[80]: 100

O(n) algorithm:

In [81]: alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]

In [82]: M = max(alist)

In [83]: max(n for n in alist if n!=M)
Out[83]: 100
inspectorG4dget
  • 110,290
  • 27
  • 149
  • 241
4

You don't have to sort the input, and this solution runs in O(n). Since your question says you cannot use builtin functions, you can use this

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
largest, larger = alist[0], alist[0]

for num in alist:
    if num > largest:
        largest, larger = num, largest
    elif num > larger:
        larger = num
print larger

Output

100

Keep track of the largest number and the second largest number (larger variable stores that in the code). If the current number is greater than the largest, current number becomes the largest, largest becomes just larger.

largest, larger = num, largest is a shortcut for

temp = largest
largest = num
larger = temp

Edit: As per OP's request in the comments,

def findLarge(myList):
    largest, larger = myList[0], myList[0]
    for num in myList:
        if num > largest:
            largest, larger = num, largest
        elif num > larger:
            larger = num
    return largest, larger

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]

firstLargest, firstLarger  = findLarge(alist[:len(alist)//2])
secondLargest, secondLarger = findLarge(alist[len(alist)//2:])

print sorted((firstLarger, firstLargest, secondLarger, secondLargest))[-2]
thefourtheye
  • 233,700
  • 52
  • 457
  • 497
  • thank you. but as i mentioned before i need use approach by dividing list into parts etc. – Manu Lakaster Oct 31 '13 at 03:12
  • @ManuLakaster But what if the `largest` and `larger` are in the first list? – thefourtheye Oct 31 '13 at 03:17
  • basically largest max in one part. larger is a second largest in part lol I wanted just divide a list into two parts, find largest and larger in each part(overall 4 numbers from two parts) and then find the second largest from 4 numbers)))) – Manu Lakaster Oct 31 '13 at 03:36
  • @ManuLakaster But why would you want to do that? – thefourtheye Oct 31 '13 at 03:42
  • I try to implement divide and conquer algorithm :) – Manu Lakaster Oct 31 '13 at 03:46
  • 1
    You just divide the list into two **once at the beginning**, but inside you don't do further division. This is not divide-and-conquer approach. You should instead call `findLarge` on two halves of the array, for each call to `findLarge`, unless there are only a certain number of elements, say 2. – justhalf Oct 31 '13 at 03:56
  • @thefourtheye for secondLargest, secondLarger it gives me the same two numbers.... – Manu Lakaster Oct 31 '13 at 04:00
  • @ManuLakaster It gives `10 90 100 706` for me. – thefourtheye Oct 31 '13 at 04:01
4

If you want an approach that consist in dividing the list, the nearest thing I can think in, is a MergeSort, it works dividing the list in 2, but it sorts a list. Then you can take the last 2 elements.

alist = [1, 7, 3, 2, 8, 5, 6, 4]

def find_2_largest(alist):
    sorted_list = mergesort(alist)
    return (sorted_list[-2], sorted_list[-1])    

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def mergesort(alist):
    if len(alist) < 2:
        return alist
    middle = len(alist) / 2
    left = mergesort(alist[:middle])
    right = mergesort(alist[middle:])
    return merge(left, right)

print find_2_largest(alist)
Christian Tapia
  • 33,620
  • 7
  • 56
  • 73
  • Downvoted because this is so much code. In practice python's sorting function runs faster that mergesort and if you really care about speed then you should do it in O(n) instead of O(n*log(n)) – placeybordeaux Oct 31 '13 at 03:42
  • 1
    @Manu Lakaster This is a well-known sort algorithm, try searching on http://en.wikipedia.org/wiki/Merge_sort, there is an animation, so you will understand how this algorithm works. **Remember** it's just sorting the list. PeterMichealLacey-Bordeaux yes, I just posted this 'approach' because of the OP requirement to make it dividing the list. – Christian Tapia Oct 31 '13 at 03:47
  • 1
    +1 because OP asked about dividing the list and because 'so much code' is sometimes exactly the right amount of code. – GnomeDePlume Sep 30 '14 at 09:08
2

O(n) solution

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
m = alist[:2] #m will hold 2 values, fill it with the first two values of alist
for num in alist:
    m = sorted(m + [num],reverse=True)[:2] #appends num to m and sorts it, takes only top 2
m[1] #the second highest element.

EDIT: changed to work with negative numbers. Basic description as follows

First I set m to be the first two elements of alist. As I iterate through alist I will be adding one value to the end of m, then sorting the three elements and throwing away the smallest one. This ensures that at the end m will contain the top two largest elements.

placeybordeaux
  • 2,138
  • 1
  • 20
  • 42
  • 1
    Can you give more explanation? Then I can +1 this =D – justhalf Oct 31 '13 at 02:49
  • @ManuLakaster That's because you don't have to do it at all. The built-in function `sorted` handles it. – aIKid Oct 31 '13 at 02:54
  • @ManuLakaster By the way, your logic has a flaw, you can't ensure if both of `second` and `first` numbers are in the same part of the list. – aIKid Oct 31 '13 at 02:56
  • 1
    You'll have a problem if all the numbers in alist are negative. – Cody Piersall Oct 31 '13 at 03:12
  • Fixed the complaints. I would really just recommend using sort on the original list unless speed is really needed. I just like providing the lowest possible worst case run time of stuff. – placeybordeaux Oct 31 '13 at 03:41
  • 1
    This algorithm can be extended to deal with any number `m`, to return the `m`-th maximum element. It will, however, have a running time of `O(n*m log m)` due to the sorting of a list with size `O(m)`. However, for larger m, this means simply iterating through the list and doing more inline comparisons will lead to a worst-case of `O(n * m)`. – Joost Sep 01 '14 at 11:08
2

Try this:

alist=[10, 0,3,10,90,5,-2,4,18,45,707, 100,1,-266,706, 1]
largest = alist[0]
second_largest = alist[0]
for i in range(len(alist)):
    if alist[i] > second_largest:
        second_largest = alist[i]
    if alist[i] > largest:
        tmp = second_largest
        second_largest = largest
        largest = tmp      

print(largest, second_largest)
Christian Tapia
  • 33,620
  • 7
  • 56
  • 73
  • cool. But can you divide list into two parts, find max element of those two parts, and then compare two numbers? – Manu Lakaster Oct 31 '13 at 02:52
  • An issue with that approach would appear when the 2 largest numbers are in the 'part'. Maybe you can get an idea from this **sort algorith** called Merge Sort. It works dividing the list into two parts, but it's to sort a list. http://en.wikipedia.org/wiki/Merge_sort (See Animation) – Christian Tapia Oct 31 '13 at 02:55
1

Without giving away code, I will give you my approach to solving this problem.

1.) Take your list, and sort it from least to greatest. There is a python function to handle this

2.) Split your list into two sections

3.) Compare the two sections, take the half with the largest numbers, repeat #2

4.) When either half contains only two numbers, take the first number from that list

The challenge is you will have to decide what to do if the list cannot be evenly split. Obviously, in the real world, you would sort the list and return the second from last value, but if you must do it by performing a binary split, this is how I would do it :)

samrap
  • 5,595
  • 5
  • 31
  • 56
  • 1
    I like the answer because it provides *hint* instead of giving blocks of code. – aIKid Oct 31 '13 at 02:43
  • 5
    If you already sort the list, you can just take the second last element. =D – justhalf Oct 31 '13 at 02:49
  • The OP said he cannot use a different approach. I even mentioned that in my question if you read it all the way @justhalf – samrap Oct 31 '13 at 03:35
  • @samrap: The requirement is to use "divide-and-conquer", not to use sort. Of course, you can sort using divide-and-conquer approach, like Merge Sort, but it's unnecessary here. – justhalf Oct 31 '13 at 03:43
  • @justhalf I think nobody understands my question. I think i needed to explain more.....Got confused in different approaches here ;( – Manu Lakaster Oct 31 '13 at 03:49
  • I've linked another question similar to what you're looking for, and I've given my answer here. Hope that answers your question – justhalf Oct 31 '13 at 03:50
1

Second largest number in the list:

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
second_highest_number = sorted(list(set(alist)))[-2]

If you only want the 2nd largest element in the list (in cases where the highest value may occur twice), just skip the set() and list() call.

alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
second_highest_number = sorted(alist)[-2]
Gaurav Keswani
  • 431
  • 4
  • 14
0
biggest = None
second_biggest = None

biggest = num_list[0]
if num_list[1] > biggest:
   second_biggest = num_list[1]
else:
   second_biggest = biggest
   biggest = num_list [1]

for n in num_list [2:]:
    if n >= biggest:
        biggest, second_biggest = n, biggest
    elif n >= second_biggest:
        second_biggest = n

print second_biggest
tacaswell
  • 84,579
  • 22
  • 210
  • 199
0

I'm amazed that most answers (except by Christian) didn't try to answer OP's real question of finding the solution using divide-and-conquer approach.

This question is almost identical to this question: Finding the second smallest number from the given list using divide-and-conquer, but it tries to find the least instead of the largest.

For which this is my answer:

def two_min(arr):
    n = len(arr)
    if n==2:
        if arr[0]<arr[1]:                   # Line 1
            return (arr[0], arr[1])
        else:
            return (arr[1], arr[0])
    (least_left, sec_least_left) = two_min(arr[0:n/2]) # Take the two minimum from the first half
    (least_right, sec_least_right) = two_min(arr[n/2:]) # Take the two minimum from the second half
    if least_left < least_right:            # Line 2
        least = least_left
        if least_right < sec_least_left:    # Line 3
            return (least, least_right)
        else:
            return (least, sec_least_left)
    else:
        least = least_right
        if least_left < sec_least_right:    # Line 4
            return (least, least_left)
        else:
            return (least, sec_least_right)

You can try to understand the code and change it to take the two largest. Basically you divide the array into two parts, then return the two largest numbers from the two parts. Then you compare the four numbers from the two parts, take the largest two, return.

This code has a bonus also for limiting the number of comparisons to 3n/2 - 2.

Community
  • 1
  • 1
justhalf
  • 8,960
  • 3
  • 47
  • 74
0
alist = [-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
largest = 0
second_largest = 0
for large in alist:
  if second_largest < large:
    second_largest = large

  if largest < large:
    temp = second_largest
    second_largest = largest
    largest = temp

print "First Highest:- %s" %largest
print "Second Highest:- %s" %second_largest
Rohan Chavan
  • 19
  • 2
0
alist=[10, 0,3,10,90,5,-2,4,18,45,707, 100,1,-266,706, 1]
print(max(alist))
second_largest=alist[0]
for i in range(len(alist)):
    if (alist[i]>second_largest and alist[i]!=max(alist)):
        second_largest=alist[i]
print(second_largest)
Timo
  • 1
0
 list1=[1,10,2,3,5,7,1,-32,90,99,99]
 max=0
 secmax=0
 for i in list1:
    if i>max:
       max=i
 for i in list1:
    if i>secmax and max!=i:
      secmax=i
 print(secmax)
pydev
  • 1
  • 1
  • 1
    Could you please elaborate a bit *why* and *how* this code snippet provides an answer to the question? Thank you. – deHaar Dec 04 '19 at 10:54
  • First find largest number in the list and stored the value in to max, Next loop the same list check the value are not equal to max and find largest number so you get second largest number – pydev Dec 04 '19 at 11:22
0
alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
sorted_list = sorted(set(alist))
sorted_list.pop()
print(max(sorted_list))
Immanuel Raj
  • 16
  • 4
-1

Here is my program, irrespective of complexity

if __name__ == '__main__':
    alist=[-45,0,3,10,90,5,-2,4,18,45,100,1,-266,706]
    alist1 = [ ]
    [alist1.append(x) for x in alist if x not in alist1]
    alist1.sort()
    print alist1[-2]
Su_scriptingbee
  • 7
  • 4