如果不使用额外的O(n)空间或散列，我们能在O(n)时间内找到数组的模式吗而且数据没有排序？
最佳答案
这个问题不容易，那么Element distinctness problem 1 -基本上没有额外的空间-问题的复杂性是Theta(nlogn)最多（并且因为它可以在Theta(nlogn)中完成-它是不适用的）。
所以基本上-如果不能为哈希表使用额外的空间，最好的方法是排序和迭代，即Theta(nlogn)。
（1）对于这个问题，给定一个在O(f(n))中运行的算法A，很容易看出可以运行A，然后通过额外的迭代来验证结果元素重复多次，以解决O(f(n) + n)中的元素区分问题。