我想请问有没有一种算法可以找到，在一个长度为n的数组中，是否有一个数组元素具有一定的频率百分比(10%、20%等。 .) 在线性时间内。
选择排序是O(n^2)，多数算法即使O(n)也只能找到数字是否重复至少n/2次.
最佳答案
假设你没有空间限制，你把它弄得比实际要难得多。
想法是迭代数组并在这样做时保存每个元素的计数。字典(或等效结构)查找的复杂度为 O(1)，所以这不是问题。
然后遍历字典并查看哪些元素具有所需的频率。
Python 伪代码:
for elem in array:
count[elem] = count.get(elem, 0) + 1
for elem, elem_count in count.items():
if 0.20 <= float(elem_count) / len(array) <= 0.25:
print "{} has a frequency between 20% and 25%".format(elem)
关于arrays - 时间 O(n) 中数组内元素的频率算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24881533/