最初の方法:- すべての行がソートされるため、最小ヒープを使用して M 配列を 1 つにマージするという概念を使用できます。手順は次のとおりです。- 各行の最初の要素をヒープに含め、最小要素を削除し、最小要素が削除された行から次の要素を含めます (最初の最小値は matrix[0][0] obv になります)。k 回実行すると、複雑さは O(klogM) になります
2 番目の方法:- 最初の方法では、列も並べ替えられるという事実を使用しませんでした。
ここでの考え方は、最小要素がヒープから削除されたときに、右側と下部の要素をヒープに挿入することです (既にヒープにない限り) 行列が次のようになっているとしましょう:-
5 7 8 9
6 9 10 13
7 11 12 15
8 13 16 17
最小要素が行列[0][0]であることはわかっているので、k=1 の場合 ans は 5 になります最初のステップで、7(0,1) と 6(1,0) を含めることができます (そして、matrix[0][1]=-1 と matrix[1][0]=-1 を作成して、後でどの要素がヒープ内にあるかがわかります) ヒープに入れると、6(1,0) が 2 番目の最小値になります。
次のステップ 9(1,1) と 7(2,0) が追加されます。
これで 7(0,1) が削除され、8(0,2) が追加されます ( 9(1,1) は既にヒープにあるため、既にあることを明確にするために、行列 -1 にこのエントリを作成しましたヒープ内)。このようにして、各ステップで 1 つの要素が削除され、最大で 2 つの要素が追加されるため、ヒープからそのような削除を k 回行った後、k 個の最小要素を取得します。
ここで、複雑さは O(klogk) になります。これは、最大で logk がヒープの高さであり、ヒープに対して k 回操作を行っているためです。間違っている場合は修正してください。
2 番目のアイデアは、一見したほうがよく見えます。ただし、M
klogk より大きい k が klogM より大きい場合。
では、k が M 未満の場合は 2 番目の方法が優れており、k が M より大きい場合は最初の方法が優れているということですか?? ここで、k はすべてのステップでインクリメントされ、高さも k が別の 2 のべき乗と交差することでインクリメントされるためです。
私の質問は、2 番目のアプローチの複雑さが本当に O(klogk) かどうかです。それとも、慎重な分析によって、それは何かより少ないのでしょうか?