Как я могу определить частоту элементов плавающего массива? - PullRequest
0 голосов
/ 19 марта 2019

Мне нужно спроектировать алгоритм сложности O (n), который определяет наиболее частый элемент в массиве, но я также должен учитывать плавающую точку или двойные элементы.Как я могу определить их частоту?

1 Ответ

0 голосов
/ 19 марта 2019

Вам необходимо определить, какая ошибка может быть в ваших сравнениях с плавающей запятой.

Самый простой способ сделать это - построить гистограмму. С гистограммой все, что рассматривается между двумя значениями (высокое значение и низкое значение), находится в области подсчета для этого диапазона.

Например, если бы у меня была гистограмма чисел от 0 до 1 с разрешением 0,2, моя гистограмма могла бы сломаться как

[0.0 - 0.2)  (5 items)
[0.2 - 0.4)  (8 items)
[0.4 - 0.6)  (3 items)
[0.6 - 0.8)  (1 item)
[0.8 - 1.0)  (0 items)

С достаточно точным диапазоном вы можете найти наиболее частый элемент в диапазоне значений.

Возможно также найти наиболее частый элемент поплавков; но это, вероятно, не даст вам необходимых результатов, потому что плавающие по своей природе содержат ошибки, что означает, что многие плавающие не будут одинаковыми, даже если они концептуально совпадают.

Поскольку существует ошибка в значении с плавающей запятой (ошибка между тем, что компьютер может хранить и значением в реальном мире), любой подход, который не обрабатывает некоторый диапазон ошибок, вряд ли даст правильные значения, и любой подход который обрабатывает некоторый диапазон ошибок, даст приблизительный ответ. Это зависит от вас, чтобы настроить подход к соответствующему количеству аппроксимации, которая все еще работает с вашим набором данных и имеющейся проблемой.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...