assume
[1,2,4,4,3,3,3]
and upper_limit is 8 (all numbers are not bigger than upper_limit)
how to produce 3 under the help of upper_limit must run in O(n+upper_limit) overall time.
Asked
Active
Viewed 60 times
-1
-
This might help you http://stackoverflow.com/questions/10797819/finding-the-mode-of-a-list – SuperTetelman Mar 14 '17 at 02:35
-
3Possible duplicate of [Finding the mode of a list](http://stackoverflow.com/questions/10797819/finding-the-mode-of-a-list) – SuperTetelman Mar 14 '17 at 02:37
2 Answers
1
a = [1,1,2,2,2,3,3,4]
cnt = {}
most = a[0]
for x in a:
if x not in cnt:
cnt[x] = 0
cnt[x] += 1
if cnt[x] > cnt[most]:
most = x
print(most)
baNv
- 493
- 1
- 4
- 12
-
-
@Lindadadad That means define an empty dict names cnt. An item in a dict has a key and a value. You need to add the key first before you using it. – baNv Mar 14 '17 at 03:29
0
You can use collections.Counter
from collections import Counter
lst = [1,2,4,4,3,3,3]
counter = Counter(lst)
most_freq, freq = counter.most_common()[0]
Alternatives to Counter using dictionary.
from collections import defaultdict
d = defaultdict(int)
lst = [1,2,4,4,3,3,3]
for val in lst:
d[val] = d[val] + 1
most_freq, freq = max(d.items(), key = lambda t: t[1])
This example keeps track of the most frequent as you iterate through circumventing the need for max function.
from collections import defaultdict
d = defaultdict(int)
lst = [1,2,4,4,3,3,3]
most_freq, freq = None, 0
for val in lst:
d[val] = d[val] + 1
if d[val] > freq:
most_freq = val
freq = d[val]
print(most_freq, freq)
If you don't want to use a defaultdict then you can just use a normal dictionary and use dict.setdefault instead.
d = {} # set d to dict
d[val] = d.setdefault(val, 0) + 1
Steven Summers
- 5,079
- 2
- 20
- 31
-
Is it your contention that this is O(n)? Because I can see nothing in the docs that indicates this. – paxdiablo Mar 14 '17 at 02:45
-
yes, btw, do you know how to code by using while loop and for loop? – Linda dadad Mar 14 '17 at 02:50
-
You can achieve a similar thing using a dictionary, which will be `O(n + len(dict))` the `Counter` is faster than with a dictionary but I believe it would be roughly the same. – Steven Summers Mar 14 '17 at 02:51
-
@Lindadadad Yes, I know how to use a for loop and while loop. What about it? – Steven Summers Mar 14 '17 at 02:53
-
Could you show me how to code with loop? i've seen many methods using collections.counter except loop! Thanks – Linda dadad Mar 14 '17 at 02:58