用于查找连续出现的数字的算法 - C++

Question

我需要一个帮助来制作一个解决一个问题的算法:有一行数字在行中出现不同的时间,我需要找到最多出现的数字以及它在行中的次数,例如:

1-1-5-1-3-7-2-1-8-9-1-2

这将是1,它出现5次.

算法应该很快(这是我的问题).有任何想法吗？

Answer 1

您正在寻找的是模式.您可以对数组进行排序,然后查找最长的重复序列.

@Jason,当你说'只是dictinary'时,你不认为计算一个*任意大*数的哈希值的复杂性也应该被考虑在内,对吗？ (3认同)
这是'O(n log n)`时间和'O(1)`空间.通过放弃空间,您可以在"O(n)"中执行此操作.显然这是最好的. (2认同)
杰森:显然,决定"最好"(和"更好")取决于*所有*要求,而OP几乎没有列出任何时间或空间要求.另外,虽然哈希表中的查找和插入是O(1),但这并不是完整的故事 - 一般来说,大的符号隐藏了重要的考虑因素,即使它本身是有用的. (2认同)

Answer 2

您可以保留哈希表并存储该结构中每个元素的计数,如下所示

h[1] = 5
h[5] = 1
...

实际上,"哈希表"与`std :: map`不同.在**哈希表**中,键是*hashed*或转换为唯一值,然后用作容器的索引.`std :: map`是[key,value]对的容器.一些实现可以通过提供哈希表来增强STL. (5认同)
现在有`std :: tr1 :: unordered_map`. (3认同)

Answer 3

你不能比线性时间更快地得到它,因为你需要至少查看每个数字一次.

如果您知道数字在某个范围内,您可以使用其他数组来总结每个数字的出现次数,否则您需要一个稍微慢一点的哈希表.

这两个都需要额外的空间,你需要在最后再次遍历计数以获得结果.

除非你真的有大量的数字并且绝对需要O(n)运行时,否则你可以简单地对数组进行排序.然后,您可以遍历数字,只需将当前数字和数字的计数与两个变量中出现的最大值保持一致.所以你节省了很多空间,用一点时间来换取它.

在某些输入案例中,您不需要查看每个输入数字以找到最多的输入数字,但您仍然*需要查看每个输入数字以查找"[最频繁的一个]是多少次在行中".弗兰克是对的. (5认同)
"你需要至少一次查看每个数字." - 这个陈述是错误的. (3认同)