0

Can we find the mode of an array in O(n) time without using Additional O(n) space, nor Hash. Moreover the data is not sorted?

4

3 に答える 3

1

問題は要素の区別の問題1よりも簡単ではありません-したがって、基本的に追加のスペースがない場合-問題の複雑さはTheta(nlogn)せいぜいです（そしてそれはで行うことができるのでTheta(nlogn)-それは事実です）。

つまり、基本的に、ハッシュテーブルに余分なスペースを使用できない場合は、並べ替えと反復を行うのが最適です。これはTheta(nlogn)です。

（1）この問題を実行するアルゴリズムAが与えられた場合、Aを実行しO(f(n))て、結果の要素が追加の反復で複数回繰り返されることを確認して、の要素の識別性の問題を解決できることを簡単に確認できますO(f(n) + n)。

于 2012-12-02T20:24:53.577 に答える
1

適切な状況下では、そうです。たとえば、データが基数ソートに適している場合は、線形時間で一定の余分なスペースのみを使用してソートし、その後、ソートされたデータを線形スキャンしてモードを見つけることができます。

データに比較ベースの並べ替えが必要な場合は、O（N log N）が一般的な場合とほぼ同じであると確信しています。

于 2012-12-02T21:38:46.517 に答える
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 に答える