欠落整数

-4

可能重複見つける：
question about missing element in array
decrease runtime to O(n) 欠落整数

を配列A [1 n]が欠落したもの数を除いて0からnまでのすべての整数を含みます。この問題では、Aの整数全体に1回の操作でアクセスすることはできません。 Aの要素はバイナリで表現されています。これらの要素にアクセスするために使用できる唯一の操作は、 "一定の時間を要するA [i]のj番目ビットをフェッチする"ことです。私たちはそれをO（n）時に行うことができますか？

出典

2011-01-17 algo-geeks

「A」の要素がバイナリで整数を表す文字列であることを意味しますか？ – birryree

@birryreeコメントをするだけのためにanythngを書いてください...意味のあるものを書いてください。 –

prp、これは以前に（そして答えられた）SOに尋ねられました。将来質問をする前に検索を行うことを提案してください：http://stackoverflow.com/questions/2946056/question-about-missing-element-in-arrayそして、将来あなたの宿題をやってみたいと思うかもしれません： – paxdiablo

はい、O（n）で実行できます。しかし、それがあなたの宿題であれば、自分で試してみるべきです。

出典

2011-01-17 04:55:11

thnx私はそれを解決することができます... –

どのようにして未知の値をバイナリ検索できますか？ – Apalala

@Apalala：ソートされた配列が必要です。配列がソートされていない場合、これは不可能です。このコメントをありがとう。 –

答えて

関連する問題