O(n)
不使用附加O(n)
空间,也不使用Hash,能否及时找到数组的众数。而且数据没有排序?
问问题
1620 次
3 回答
1
在适当的情况下,是的。例如,如果您的数据适合基数排序,那么您可以在线性时间内仅使用恒定的额外空间进行排序,然后对已排序的数据进行线性扫描以查找模式。
如果您的数据需要基于比较的排序,那么我很确定 O(N log N) 与您在一般情况下可以做的差不多。
于 2012-12-02T21:38:46.517 回答
1
这个问题并不比元素区别问题1更容易- 所以基本上没有额外的空间 - 问题的复杂性Theta(nlogn)
充其量是(并且因为它可以完成Theta(nlogn)
- 它是必要的)。
所以基本上 - 如果你不能为哈希表使用额外的空间,最好是排序和迭代,即Theta(nlogn)
.
(1) 给定一个针对该问题运行的算法 A,O(f(n))
很容易看出可以运行 A,然后通过额外的迭代验证结果元素是否重复一次以上,以解决 中的元素区别性问题O(f(n) + n)
。
于 2012-12-02T20:24:53.577 回答
0
只计算频率。这不是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 也可以很小。无论如何,这确实可以正确回答您的问题,即使它不切实际。
于 2012-12-02T20:03:12.543 回答