How to find the second largest number


#1

I have been thinking.
If I use Max( ) to find the maximum number and Min( ) for the smallest, how can I find the second largest number ?

https://www.codecademy.com/en/courses/python-beginner-c7VZg/3/2?curriculum_id=4f89dab3d788890003000096


Replace this line with your code.


#2

How would you do it manually? Start there.
You'll also have to decide on what you consider to be second largest when there are two of the largest value.


#3

I think that the best option would be like to set the maximum number and then just discard it.(or make it invisible or some sort) and make the program search again for the maximum number.

Not sure if my line of though is the best one though.


#4

If you had numbers written on a paper, would you really erase the largest one and then search again?

I do believe you'd only need to scan through them all once, while remembering the largest two.


#5

If i had on a sheet of paper I would begin by searching for the biggest number of the list and circle it. Then repeat the process to find the second largest.


#6

You'll have to analyse how you find the biggest one though. It'll be by comparison with the currently largest the whole time, and then you can just as well keep track of two.

What if you were to find the nth largest one? (A function, that given n and a sequence, finds the nth largest value in the sequence)


#7

The function to find the largest number in the sequence would be -> .max( ) <-
But then i get stuck.


#8

forget max, you would be implementing a function doing something similar but slightly different.

max would start with the first element and then walking through the sequence and update the highest known value as it goes.

for second largest one would instead keep track of both the highest and second highest while going through the list

for nth highest, one could have a list of size n with the n largest known values so far which is updated while going through the list. However, this adds up to quite a lot of operations for a large n and a large sequence and it would be better to just sort the sequence. It can still be done in linear time but this requires an algorithm (quickselect) that takes a bit more time to come up with than it takes to just type it out. So if you can get away with sorting it then you might not want to optimize any further in the interest of keeping the code simple.


#9

Thank You so much. I believe i understood, I will trying it out by what you have explained.


#10

Btw, finding the nth largest/smallest is useful for finding a median. There too, the naive version is to sort it. But if the nth largest can be found in linear time, then the median can also be found in linear time. (sorting takes n log n time)

And in summary, quickselect goes something like:

pick a random element from the sequence
put all smaller in one list
put all equal or greater in another list
determine which of the two lists the nth value is in based on their sizes and n
repeat from top until found

There are other ways of choosing that pivot to divide the sequence by that one might want to use for more consistent results. Random is a good method for average performance though.


#11

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.