この質問の意味を理解していますか
線形時間未満で整数の配列内の上位log（n）または上位sqt（n）値を検索します。
そうでない場合は、ここに質問http://www.careercup.com/question?id=9337669があります。
この質問を理解するのを手伝っていただければ、解決できるかもしれません。（私が理解したら、私もそれを解決するかもしれませんが）
御時間ありがとうございます。
質問する
604 次
2 に答える
6
ソートされていない配列の場合、複雑さは線形ですが、log（n）とsqrt（n）が両方とも単調成長関数であるため、max（log（n）、...）もlog（max（n、...））およびsqrtについても同じです。
したがって、max（n）を（線形に）見つけて、logとsqrtを計算します。
于 2011-12-21T08:50:16.640 に答える
3
配列がソートされていないと仮定すると、この問題はOmega(n)、すべての要素を読み取る必要があるためです[Omega(n)ソートされていない配列では最大値を見つけることが問題であり、この問題は最大値を見つけるよりも簡単ではありません]。したがって、それに対する劣線形解はありません。
選択アルゴリズムO(n)を使用した[線形]ソリューションがあります
1. find the log(n) biggest element. //or sqrt(n) biggest element...
2. scan the array and return all elements bigger/equal it.
（*）配列に重複が含まれている場合、この擬似コードは正しくありませんが、2番目のステップで重複をトリミングするのはかなり簡単です。
于 2011-12-21T08:18:54.443 に答える