2

below I've listed a problem I'm having some trouble with. This problem is a simple nested loop away from an O(n^2) solution, but I need it to be O(n). Any ideas how this should be tackled? Would it be possible to form two equations?

Given an integer array A, check if there are two indices i and j such that A[j] = 2∗A[i]. For example, on the array (25, 13, 16, 7, 8) the algorithm should output “true” (since 16 = 2 * 8), whereas on the array (25, 17, 44, 24) the algorithm should output “false”. Describe an algorithm for this problem with worst-case running time that is better than O(n^2), where n is the length of A.

Thanks!

4

2 に答える 2

6

これは、ハッシュ テーブルを使用するのに最適な場所です。ハッシュ テーブルを作成し、配列内の各数値をハッシュ テーブルに入力します。次に、配列全体をもう一度繰り返し、各 i のハッシュ テーブルに 2*A[i] が存在するかどうかを確認します。もしそうなら、このプロパティを持つインデックスのペアが存在することがわかります。そうでない場合、そのようなペアは存在しないことがわかります。

予想通り、これには O(n) の時間がかかります。これは、ハッシュ テーブルでの n 回の操作に予想される償却 O(1) 時間がかかるためです。

お役に立てれば！

于 2013-11-05T02:23:38.357 に答える