これを行う方法を私が知っている唯一の方法は、ループをネストすることです。しかし、これはO（n ^ 2）時間で実行されます。私のメンターは、インタビュー中に問題を解決するように求められ、ループをネストすることから解決を開始した場合は、問題を停止して再考する必要があると言いました。どうやら、O（n ^ 2）よりも良いルートが常にあります。しばらく考えていたのですが、グーグルでどう言い換えても答えが見つかりません。出来ますか？
2 に答える
2
どうやら、O(n^2) よりも優れたルートが常に存在するようです。
これは明らかに誤りだと思います。実際には O(n^2) である問題がいくつかあります。問題をより効率的にする特定の言語機能がない限り、 O(n^2) がネストされた配列に最適です。
于 2013-03-15T00:41:58.370 に答える
1
それが最速の方法です。
ネストされた配列構造全体にあるエントリと同じ数のエントリを調べると...まあ、明らかにそれ以上のことはできませんよね? ;)
あなたの混乱は、n = 構造の次元だと考えていることですが、実際には n = 構造の合計のエントリ数です。したがって、ネストされたループを使用するのは O(n) であり、ネストのレベルで調べるものがなくなったらすぐにループが終了します。
于 2013-03-15T00:41:08.183 に答える