我们能否在 O(n) 时间内找到数组的模式而不使用额外的 O(n) 空间，也不使用 Hash。而且数据没有排序？
最佳答案
问题没那么简单Element distinctness problem 1 - 所以基本上没有额外的空间 - 问题的复杂性是 Theta(nlogn)充其量(因为它可以在 Theta(nlogn) 中完成 - 确实如此)。
所以基本上 - 如果您不能为哈希表使用额外的空间，最好是排序和迭代，即 Theta(nlogn) .
(1) 给定算法 A 在 O(f(n)) 中运行对于这个问题，很容易看出，可以运行 A，然后通过额外的迭代验证结果元素重复多次，从而解决 O(f(n) + n) 中的元素差异性问题。 .
关于arrays - 我们能否在 O(n) 时间内在未排序的数组中找到没有 hashmap 的数组的模式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13672935/