I found this code on this site to find the second largest number:
def second_largest(numbers):
m1, m2 = None, None
for x in numbers:
if x >= m1:
m1, m2 = x, m1
elif x > m2:
m2 = x
return m2
Source: Get the second largest number in a list in linear time
Is it possible to modify this code to find the second smallest number? So for example
print second_smallest([1, 2, 3, 4]) 2
Answers:
Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.
Method 1
a = [6,5,4,4,2,1,10,1,2,48] s = set(a) # used to convert any of the list/tuple to the distinct element and sorted sequence of elements # Note: above statement will convert list into sets print sorted(s)[1]
Method 2
The function can indeed be modified to find the second smallest:
def second_smallest(numbers):
m1 = m2 = float('inf')
for x in numbers:
if x <= m1:
m1, m2 = x, m1
elif x < m2:
m2 = x
return m2
The old version relied on a Python 2 implementation detail that None is always sorted before anything else (so it tests as ‘smaller’); I replaced that with using float('inf') as the sentinel, as infinity always tests as larger than any other number. Ideally the original function should have used float('-inf') instead of None there, to not be tied to an implementation detail other Python implementations may not share.
Demo:
>>> def second_smallest(numbers):
... m1 = m2 = float('inf')
... for x in numbers:
... if x <= m1:
... m1, m2 = x, m1
... elif x < m2:
... m2 = x
... return m2
...
>>> print(second_smallest([1, 2, 3, 4]))
2
Outside of the function you found, it’s almost just as efficient to use the heapq.nsmallest() function to return the two smallest values from an iterable, and from those two pick the second (or last) value. I’ve included a variant of the unique_everseen() recipe to filter out duplicate numbers:
from heapq import nsmallest
from itertools import filterfalse
def second_smallest(numbers):
s = set()
sa = s.add
un = (sa(n) or n for n in filterfalse(s.__contains__, numbers))
return nsmallest(2, un)[-1]
Like the above implementation, this is a O(N) solution; keeping the heap variant each step takes logK time, but K is a constant here (2)!
Whatever you do, do not use sorting; that takes O(NlogN) time.
Method 3
Or just use heapq:
import heapq
def second_smallest(numbers):
return heapq.nsmallest(2, numbers)[-1]
second_smallest([1, 2, 3, 4])
# Output: 2
Method 4
As per the Python in-built function sorted
sorted(my_list)[0]
gives back the smallest number, and sorted(my_list)[1] does accordingly for the second smallest, and so on and so forth.
Method 5
My favourite way of finding the second smallest number is by eliminating the smallest number from the list and then printing the minimum from the list would return me the second smallest element of the list. The code for the task is as below:
mylist=[1,2,3,4] mylist=[x for x in mylist if x!=min(mylist)] #deletes the min element from the list print(min(mylist))
Method 6
Yes, except that code relies on a small quirk (that raises an exception in Python 3): the fact that None compares as smaller than a number.
Another value that works is float("-inf"), which is a number that is smaller than any other number.
If you use that instead of None, and just change -inf to +inf and > to <, there’s no reason it wouldn’t work.
Edit: another possibility would be to simply write -x in all the comparisons on x, e.g. do if -x <= m1: et cetera.
Method 7
Solution that returns second unique number in list with no sort:
def sec_smallest(numbers):
smallest = float('+inf')
small = float('+inf')
for i in numbers:
if i < smallest:
small = smallest
smallest = i
elif i < small and i != smallest:
small = i
return small
print('Sec_smallest:', sec_smallest([1, 2, -8, -8, -2, 0]))
Method 8
mi= min(input_list)
second_min = float('inf')
for i in input_list:
if i != mi:
if i<second_min:
second_min=i
if second_min == float('inf'):
print('not present')
else:
print(second_min)
##input_list = [6,6,6,6,6]
#input_list = [3, 1, 4, 4, 5, 5, 5, 0, 2, 2]
#input_list = [7, 2, 0, 9, -1, 8]
# Even if there is same number in the list then Python will not get confused.
Method 9
I’d like to add another, more general approach:
Here’s a recursive way of finding the i-th minimums of a given list of numbers
def find_i_minimums(numbers,i):
minimum = float('inf')
if i==0:
return []
less_than_i_minimums = find_i_minimums(numbers,i-1)
for element in numbers:
if element not in less_than_i_minimums and element < minimum:
minimum = element
return less_than_i_minimums + [minimum]
For example,
>>> find_i_minimums([0,7,4,5,21,2,6,1],3) # finding 3 minimial values for the given list [0, 1, 2]
( And if you want only the i-th minimum number you’d extract the final value of the list )
The time-complexity of the above algorithm is bad though, it is O(N*i^2) ( Since the recursion depth is i , and at each recursive call we go over all values in ‘numbers’ list whose length is N and we check if the minimum element we’re searching for isn’t in a list of length i-1, thus the total complexity can be described by a geometric sum that will give the above mentioned complexity ).
Here’s a similar but alternative-implementation whose time-complexity is O(N*i) on average. It uses python’s built-in ‘set’ data-structure:
def find_i_minimums(numbers,i):
minimum = float('inf')
if i==0:
return set()
less_than_i_minimums = find_i_minimums(numbers,i-1)
for element in numbers:
if element not in less_than_i_minimums and element < minimum:
minimum = element
return less_than_i_minimums.union(set({minimum}))
If your ‘i’ is small, you can use the implementations above and then extract how many minimums you want ( or if you want the second minimum, then in your case run the code for i=2 and just extract the last element from the output data-structure ).
But if ‘i’ is for example greater than log(N) , I’d recommend sorting the list of numbers itself ( for example, using mergesort whose complexity is O(N*log(N)) at worst case ) and then taking the i-th element. Why so? because as stated, the run-time of the algorithm above is not great for larger values of ‘i’.
Method 10
l = [41,9000,123,1337] # second smallest sorted(l)[1] 123 # second biggest sorted(l)[-2] 1337
Method 11
Here we want to keep an invariant while we scan the list of numbers, for every sublist it must be
m1<=m2<={all other elements}
the minimum length of a list for which the question (2nd smallest) is sensible is 2, so we establish the invariant examining the first and the second element of the list (no need for magic numbers), next we iterate on all the remaining numbers, maintaining our invariant.
def second_smaller(numbers):
# if len(numbers)<2: return None or otherwise raise an exception
m1, m2 = numbers[:2]
if m2<m1: m1, m2 = m2, m1
for x in numbers[2:]:
if x <= m1:
m1, m2 = x, m1
elif x < m2:
m2 = x
return m2
Addendum
BTW, the same reasoning should be applied to the second_largest function mentioned by the OP
Method 12
I am writing the code which is using recursion to find the second smallest element in a list.
def small(l):
small.counter+=1;
min=l[0];
emp=[]
for i in range(len(l)):
if l[i]<min:
min=l[i]
for i in range(len(l)):
if min==l[i]:
emp.append(i)
if small.counter==2:
print "The Second smallest element is:"+str(min)
else:
for j in range(0,len(emp)):
l.remove(min)
small(l)
small.counter = 0
list=[-1-1-1-1-1-1-1-1-1,1,1,1,1,1]
small(list)
You can test it with various input integers.
Method 13
There is a easy way to do . First sort the list and get the second item from the list.
def solution(a_list):
a_list.sort()
print a_list[1]
solution([1, 2, -8, -2, -10])
Method 14
You can use in built function ‘sorted‘
def second_smallest(numbers):
count = 0
l = []
for i in numbers:
if(i not in l):
l.append(i)
count+=1
if(count==2):
break
return max(l)
Method 15
To find second smallest in the list, use can use following approach which will work if two or more elements are repeated.
def second_smallest(numbers):
s = sorted(set(numbers))
return s[1]
Method 16
Here is:
def find_second_smallest(a: list) -> int:
first, second = float('inf')
for i in range(len(a)):
if a[i] < first:
first, second = a[i], first
elif a[i] < second and a[i] != first:
second = a[i]
return second
input: [1, 1, 1, 2]
output: 2
Method 17
This code is also works fine, To find the second smallest number in list.
For this code first we have to sort the values in list. after that we have to initialize the variable as second index.
l1 = [12,32,4,34,64,3,43]
for i in range(0,len(l1)):
for j in range(0,i+1):
if l1[i]<l1[j]:
l1[i],l1[j]=l1[j],l1[i]
min_val = l1[1]
for k in l1:
if min_val>k:
break
print(min_val)
Method 18
def SecondSmallest(x):
lowest=min(x[0],x[1])
lowest2 = max(x[0],x[1])
for item in x:
if item < lowest:
lowest2 = lowest
lowest = item
elif lowest2 > item and item > lowest:
lowest2 = item
return lowest2
SecondSmallest([10,1,-1,2,3,4,5])
All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0