0
集合aと集合bは、それぞれソートされた配列の形で与えられたn個の要素を持つ。ユニオンbと交点bを計算するO（n）時間アルゴリズムを提示する。2つのソートされた配列のUnionおよび交差のO（n）時間アルゴリズムとは何ですか？
A
答えて
0
各アレイに2つのポインタがあり、常に小さいか同じものを移動しています。
両方のポインタで2つの同じ番号を取得すると、交差点が表示されます。組合が必要な場合は、移動したものを置くだけです。 （同じ番号の重複を避けたい場合は、すでにその番号を追加しているかどうかを確認するだけです）
関連する問題
- 1. 2つの配列を比較するためのO（n）時間とO（n）空間のアルゴリズム
- 2. Count（A、B、n）アルゴリズムのBig-O（O（n））およびBig-Omega（Ω（n））時間の複雑度
- 3. このアルゴリズム（n^2）*（n^2 + 1）/ 2（つまりO（n/4））の実行時間はなぜですか？
- 4. 2つの列のソートされた差
- 5. 2^N配列の挿入ソートの時間の複雑さ？
- 6. 交差アルゴリズムO（n）より良い方法はありますか？
- 7. 2つのソート済みリストの交差のための最も速いアルゴリズムは何ですか？
- 8. なぜ配列挿入の時間複雑さはO（n）で、O（n + 1）ではないのですか？
- 9. 2つの配列を交差する
- 10. 2つのx配列データセットの交差
- 11. leetcode 349：2つの配列の交差
- 12. 実行時間がO（log（n））未満でソートされた配列から検索する
- 13. ユニークでないC++のソートされていない交差アルゴリズム
- 14. O（1）、O（n log n）、O（log n）の複雑さを持つアルゴリズムの例
- 15. 時間複雑度がO（sqrt（n）* log（n））のアルゴリズムはありますか？
- 16. 2つの同じ長さのリストを順番に組み合わせるO（n）アルゴリズムとは何ですか？
- 17. MongoDB Unionと1回の呼び出しでの交差
- 18. O（ログn）以下の削除およびアクセス時間のSTLデータ構造
- 19. O（n）とO（log（n））の違い - これはより良く、O（log（n））は正確に何ですか？
- 20. Javaコレクション：TreeMap.size（）およびTreeSet.size（）：O（1）またはO（n）？
- 21. O（n）時にn桁の0からnまでの整数の配列をソート
- 22. 2つのソートされた配列を3番目のものにマージすることはO（n）で行うことができますか？
- 23. アルゴリズムの漸近解析：時間nでソートされたリストnにk個の新しい要素を挿入する方法O（k log k + n）
- 24. o（n^2）の代わりにo（log n）またはo（n）の時間複雑度を持つようにこのコードを修正する方法
- 25. 2つの入力配列でループするソリューション：O（n + m）またはO（n * m）
- 26. 時間Oの複雑さ（n（nはをログ）ログ）+ nはO（L）
- 27. 2つのファイル間の交差
- 28. Linq配列との交差
- 29. マクロと配列の交差
- 30. OBIEE 2つの列の時間差