1

2 つの配列 A と B が与えられ、それぞれに n 個の正の数と次の式がある場合:

x^8 = y^6 + x^2y^2 + 10

前の方程式が成り立つように、A の x と B の y を見つける nlog(n) 時間で実行されるアルゴリズムを設計します。

最初に行うことは、後でバイナリ検索を使用するため、両方の配列をソートすることですが、問題は用語です

x^2y^2

方程式の両側で分離できないのはどれですか? それとも、ここで間違った道を進んでいますか？何か案は？

4

1 に答える 1

4

最初に注意すべきことは、x と y の両方が偶数乗であるということです。つまり、並べ替えるときは絶対値で並べ替える必要があります (これはまだ nlogn です)。

次に、array1 の各要素を調べて、配列 2 でバイナリ検索を実行します。関数が単調増加するため、バイナリ検索を実行できるはずです。このステップは nlogn です。

あなたが私の答えを理解していない場合は、さらに詳しく説明できます。

お知らせ下さい ：）

于 2013-04-21T06:15:38.527 に答える