Найти среднее значение списка чисел в обозначении O (1) — постоянное время
Вот в чем дело, у меня есть задача создать массив с некоторыми числами, после чего массив может принимать любые другие числа того же типа внутри в любой позиции. Когда я получу окончательный массив (с добавленными числами), мне нужно найти среднее число чисел с постоянным O (1) временем. Как я это сделал?!
Вот что я имею в качестве примера
Элементы: 5 12 7 9 31
Среднее: 12,8
Решение
Если это класс массива, вы можете отслеживать сумму всех чисел по мере их добавления и обновления. Затем, когда все обновления будут завершены, просто разделите сумму на количество элементов, чтобы получить среднее значение, и только вычисление среднего будет O (1), так как сумма была предварительно вычислена.
Если это необработанный массив памяти, который вы просто передаете, то для вычисления среднего значения потребуется суммирование всего числа, которое равно O (N), если только кто-то не играет в игру семантики, касающуюся операции.
Другие решения
Других решений пока нет …
detector