今日、TwitterのTLで以下のエントリを見かけた。
サマーインターン2011問題 : Preferred Research
http://research.preferred.jp/2011/07/intern2011_problem/
インターンの応募選考で以下のような問題が出されたらしい。
長さnの文字列中で出現回数が最大の文字をO(n)時間で答えるプログラムを書いてください。
但し、出現回数が最大の文字の出現回数はn/2より大きいとします。
条件として、文字列を格納しているバッファは書き換え可能で文字列以外に利用できるバッファサイズは
c log n bits (cは任意の定数）であり、文字種類数は可変（最大n)であるとします。
アルゴリズムが全然駄目なので、チャレンジしてみた。
O(n)ってことは、一回だけ走査して、それで見つけなきゃいけないわけだ。
10分ちょっと考えて思いついたが・・・脳内オンリーなので間違ってる可能性が。
職場で考えてそのまま書いてるので、コード書いて検証とかやってないw
思いついたのは、以下の方法。
- 文字列のバッファサイズは、定数時間で取れると想定。後、1byte文字しか考えてない。
- 文字列のバッファを中間点で前半と後半に分ける。(奇数の場合は、前半を1バイト分多めに取る)
- ワーク領域に、1byteの文字格納領域と、整数のカウントが持てる構造体とか作る。
- 前半の1文字目と、後半の1文字目を比較。
- 一致しないなら、スルーして次の文字へ。
- 一致した場合。
- ワーク領域のカウントが0なら、文字格納領域へコピーしてカウントをインクリメント。
- ワーク領域のカウントが1以上なら、文字格納領域の文字と更に比較。
- 一致したら、カウントをインクリメントする。
- 不一致ならば、カウントをデクリメントする。
これを繰り返す。
つまり最頻度文字が過半数を占めるなら、半分で割れば少なくとも1回は一致する・・・と思うw
他で一致する文字があったとしても最頻度文字の方が多く一致する・・・はずw
文字数が偶数なら、最頻度文字がワーク領域に残る。
文字数が奇数なら最後に1文字残るけど、カウントが0だったら、残った奴が最頻度文字で、
カウントが1以上だったら、ワーク領域にあるのが最頻度文字。
これで、一回線形探索するだけで、最頻度文字が分かるので、O(n)になるんじゃないかな。
うーん、合ってんのかな？なんか、3通りぐらい正解例があるらしいけど。
コンピュータ関連の知識は、全部趣味の独学ベースなので、こういう情報工学の基礎的なところが全然駄目なんだよなあ。
間違ってたら、突っ込んでやってください。
