Рассчитать режим ввода списка - PullRequest
Новая
       3

Рассчитать режим ввода списка

0 голосов
/ 19 апреля 2020

Я занимаюсь улучшением своего кода. Это функция, которая вычисляет наиболее распространенное число во входном списке и возвращает наименьшее число, если более одного числа встречается одинаковое количество раз 

def mode(list):
    """ Calculates the mode of a list. Takes a list as argument"""
    current_count = 0
    a = max(list) + 1
    num_elements = [0]*a
    val = 0
    for i in range(len(list)):
        num_elements[list[i]] += 1
    for i in range(a):
        if num_elements[i] > current_count:
            current_count = num_elements[i]
            val = i
    return val

К сожалению, эта функция теперь имеет псевдополином сложность времени, и я хочу, чтобы она имела среднюю сложность времени n. Каков наилучший способ сделать это?

1 Ответ

0 голосов
/ 19 апреля 2020

Вы добавляете ненужную сложность псевдополиномиального времени, выполняя 

a = max(list) + 1
for i in range(a):
   ...

и, таким образом, делая ненужные итерации.
Чтобы функция была линейной по размеру ввода, вы можете создать ассоциацию (т.е. , словарь element-> repetitions ) и затем взять элемент минимального значения, встречающийся чаще всего. 

from collections import defaultdict

def mode(l):
   # count occurrences (you could also use a Counter)
   d = defaultdict(int)
   for el in l:
      d[el]+=1
   # take the highest number of occurrences
   highest_occurrences = max(d.values())
   # return the element of minimum value with the highest number of occurrences
   return min(el for el in d if d[el]==highest_occurrences)
...