Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
2 つの配列 A と B が与えられ、それぞれに n 個の正の数と次の式がある場合:
x^8 = y^6 + x^2y^2 + 10
前の方程式が成り立つように、A の x と B の y を見つける nlog(n) 時間で実行されるアルゴリズムを設計します。
最初に行うことは、後でバイナリ検索を使用するため、両方の配列をソートすることですが、問題は用語です
x^2y^2
方程式の両側で分離できないのはどれですか? それとも、ここで間違った道を進んでいますか?何か案は?
最初に注意すべきことは、x と y の両方が偶数乗であるということです。つまり、並べ替えるときは絶対値で並べ替える必要があります (これはまだ nlogn です)。
次に、array1 の各要素を調べて、配列 2 でバイナリ検索を実行します。関数が単調増加するため、バイナリ検索を実行できるはずです。このステップは nlogn です。
あなたが私の答えを理解していない場合は、さらに詳しく説明できます。
お知らせ下さい :)