I need a solution that is O(n) for finding most repeated element in a list. If 2 or more numbers are repeated the same amount of time return smallest number.
from collections import Counter
def most_frequent(n):
count_occurence = Counter(n)
return count_occurence.most_common(1)[0][0]
input = [2,4,4,5,2,3,3,4,5,6,6,6,1]
Output should be 4 which should give the count of 3
Advertisement
Answer
You could use max and groupby:
from itertools import groupby
def most_frequent(li):
maxes=[]
for k,g in groupby(sorted(li)):
maxes.append((len(list(g)), -k))
return -max(maxes)[1]
Or use a dict as a counter:
def most_frequent(li):
cnt={}
for e in li:
cnt[-e]=cnt.get(-e, 0)+1
return -max(cnt.items(), key=lambda t: (t[1],t[0]))[0]
Or if your data has runs of similar numbers, without the O(n log n) sort step you can combine these two methods:
def most_frequent(li):
cnt={}
for k,g in groupby(li):
cnt[-k]=cnt.get(-k,0)+len(list(g))
return -max(cnt.items(), key=lambda t: (t[1],t[0]))[0]
And it likely is the case that using max on a comprehension is faster than using a lambda:
def most_frequent(li):
cnt={}
for k,g in groupby(li):
cnt[-k]=cnt.get(-k,0)+len(list(g))
return -max(((y,x) for x,y in cnt.items()))[1]
In all cases, you are construction a tuple of (-element_in_list, count_of_that_element):
cnt=[(-2, 2), (-4, 3), (-5, 2), (-3, 2), (-6, 3), (-1, 1)]
You then take that max of that by reversing the tuple either with a comprehension of a key function. Your answer then is -element_in_list since it was negated to take the max.