arrays - 我们可以在 O(n) 时间内在未排序的数组中找到没有 hashmap 的数组的模式吗

Question

O(n)不使用附加O(n)空间，也不使用Hash，能否及时找到数组的众数。而且数据没有排序？

Answer 1

在适当的情况下，是的。例如，如果您的数据适合基数排序，那么您可以在线性时间内仅使用恒定的额外空间进行排序，然后对已排序的数据进行线性扫描以查找模式。

如果您的数据需要基于比较的排序，那么我很确定 O(N log N) 与您在一般情况下可以做的差不多。

Answer 2

这个问题并不比元素区别问题¹更容易- 所以基本上没有额外的空间 - 问题的复杂性Theta(nlogn)充其量是（并且因为它可以完成Theta(nlogn)- 它是必要的）。

所以基本上 - 如果你不能为哈希表使用额外的空间，最好是排序和迭代，即Theta(nlogn).

---

(1) 给定一个针对该问题运行的算法 A，O(f(n))很容易看出可以运行 A，然后通过额外的迭代验证结果元素是否重复一次以上，以解决 中的元素区别性问题O(f(n) + n)。

Answer 3

只计算频率。这不是O(n)空格，而是O(k)，其中 k 是范围内不同值的数量。这实际上是一个常数空间。

时间显然是线性的 O(n)

//init
counts = array[k]
for i = 0 to k
    counts[i] = 0

maxCnt = 0
maxVal = vals[0]
for val in vals
    counts[val]++
    if (counts[val] > maxCnt)
        maxCnt = counts[val]
        maxVal = val

这里的主要问题是，虽然 k 可能是一个常数，但它也可能非常非常大。然而，k 也可以很小。无论如何，这确实可以正确回答您的问题，即使它不切实际。