アレイが与えられた場合、アレイのコインプライムサブアレイの数をO(N²)時間よりも長く見つけることは可能ですか? Co-Prime配列は、すべての要素のGCDが1になるように、配列の連続したサブセットとして定義されます。コプライムサブアレイを見つける効率的なアプローチ
答えて
配列の最後に1つの要素を追加することを検討してください。ここで右端の位置があれば、その位置から追加した要素までのサブ配列がコプライムになるようにします。それが右端であるため、追加された要素で終わる短い配列はコプリムではありません。それはコプリムであるため、左に始まり新しい要素で終わるすべての配列はコプライム(co-prime)です。したがって、新しい要素で終わるコプライムサブアレイの数を計算しました。 O(n)の代わりにO(log n)のように右端の位置を効率的に見つけることができれば、O(n log n)のコプライムサブアレイの数を、時間。
右端の位置を見つけることができるようにするには、完全な配列を完全な2分木の葉として考え、その長さを2の累乗にするようにパディングします。各ノードで、そのノードの下にあるすべての要素のGCDを入力します。これは時間O(n)のボトムアップから行うことができます。配列内の連続したすべての区間は、ノードの下にある葉から間隔がくるように、サイズO(log n)のノードの集合でカバーすることができるため、区間のGCDを時間O(log n)として計算できます。
現在の要素との間でコニ係数サブアレイを形成する最も右の位置を見つけるには、現在の要素から始め、それが1であるかどうかを確認します。そうでない場合は、要素を左に見てGCDを取り出し、結果をスタックにプッシュします。結果が1の場合は終了し、そうでない場合は終了しますが、2つの要素のサブツリーが存在するかどうかを調べて、2つの要素を同時に追加できます。後続の各ステップで、検索しようとしているサブツリーのサイズを2倍にします。あなたはいつも好きなサイズの便利なサブツリーを見つけることはできませんが、すべての間隔をO(log n)サブツリーでカバーすることができるので、時間O(log n)のこのステップをたどるのに十分なことがよくあるでしょう。
現在、現在の要素の配列全体がコプライムでないか、またはコプライムであるセクションが見つかったが、必要以上に左に移動する可能性があります。スタックの一番上にある値は、GCDをそのスタックのすぐ下の値で、GCDをサブツリーの上部に置くことによって計算されました。それをスタックからポップし、その直下の値とサブツリーの右半分のGCDを取る。あなたがまだコプライムであれば、サブツリーの左半分は必要ありません。そうでなければ、あなたはそれを必要としましたが、おそらくすべてではありません。いずれの場合でも、時間O(log n)の中で最も右の一致を見つけるために継続することができます。
だから、私はあなたが時間の現在の要素を持つコインプライムサブアレイを形成することができると思う(おそらくいくつかの非常に厄介なプログラミングと)間違ったサブアレイの数を数えることができます時間O(NログN)
二つの例:
リスト1、3、5、7次のレベルは1,1であり、現在の要素が13である場合、ルートは1であるが、私は反対チェックしたがって、GCD(5,7,13)= GCD(3,5,7,13)= GCD(1,3,4,7,13)は、 = 1
リスト2,4,8,16次のレベル現在の数字が32の場合、16と照合してgcd(16,32)= 16!= 1を見つけたら、8と照合してそのGCD(8,32)を見つけます。 )= 8とし、GCD(2,32)= 2でGCD = 1の拡張配列に区間がないことを確認します。
あなたは、ツリーが全ての以前の要素との比較を避けるのにどのように役立つかを示す例を与えてください。私はそれがいかに可能かはわかりません。 –
例を追加しました。私は、コモンレームのリストが何であるかに同意できない可能性があると思います。私は、リストのすべての要素を分割する最大の数が1であることを意味します。 – mcdowella
ありがとう!しかし、申し訳ありませんが、私はまだそれを取得しません。 [a、b]が共起していることを知っているならば、(c、b)のGCDと(c、a)のGCDを見つけることなく[a、b、c]が共起することをどのように知ることができますか? –
- 1. ワイルドカードエントリを効率的に見つける
- 2. マッピングを効率的に見つける
- 3. カーネル:pidでtask_structを見つける効率的な方法は?
- 4. 「テーブル」で値を見つける効率的な方法C#
- 5. 効率的なマルチスレッドセット差へのアプローチ
- 6. btwフィルタとループの効率的なアプローチ
- 7. ASP.NET効率的なチャットアプリケーションのアプローチ
- 8. 効率的にオーバーラップするJodaTimeインターバルを見つける
- 9. テキストファイルの最後の行を効率的に見つける
- 10. 効率的に重複のペアの数を見つける
- 11. 行の配列の交差を効率的に見つける
- 12. 一意の置換を効率的に見つける
- 13. データフレーム内のヌル値を効率的に見つける方法
- 14. ポイントクラウド間の距離を効率的に見つける
- 15. Excel残りの列を効率的に見つける
- 16. 整数の等しくないパーティションを見つける効率的な方法
- 17. 値のリストと一致する行を見つける効率的な方法
- 18. 効率的なデータベースを構築するためのアプローチ
- 19. 80+テーブルで最大値を見つける効率的な方法
- 20. 効率的な方法でPythonの文字列を見つける
- 21. 単語のリストに「フック単語」を見つける効率的な方法は?
- 22. リスト内の隣人を見つける最も効率的な方法
- 23. タグと属性でノードを見つける効率的な方法
- 24. MATLAB行列の要素を見つけるための効率的な方法
- 25. 配列内のマスター要素を見つける効率的なアルゴリズム?
- 26. ソースコードファイルの小さなタイプミスを効率的に見つける方法は?
- 27. 効率的な方法で、javaのマトリックスで "一致"を見つける
- 28. numpy配列でモードを見つける最も効率的な方法
- 29. 2つのcsvファイルの違いを効率的に見つける
- 30. ジェネリックは、私はこのアプローチが有効で見つける
私は2つの数字のGCDを見つけることは、この場合一定の時間とみなされる。 – biziclop
@biziclop ...yes – yobro97