疑似コードを書き、関数の実行時間を分析するように求められました。
2 つの降順で並べ替えられた配列と 1 つの整数 k が与えられ、2 つの配列の和集合で k 番目に大きい数を見つけるように求められます。
割り当ての期日がまだ過ぎていないため、コードを実行しました。申し訳ありませんが、ここにコードを投稿できません。
いくつかの欠陥があります。質問 1: k>sum(arraylen(a & b)) のようなシナリオを処理する必要があるかどうか、または指定された 2 つの配列が空の場合のシナリオを処理する必要があるかどうかわかりません。戻り値を使用する必要がありますか? -1? k 番目に大きい値が正確に -1 の場合はどうなるでしょうか....よくわかりません。
質問 2: 配列の長さを取得しようとしたとき、sizeof(ArrayA)/4、(C++) を使用しsizeofました。 ArrayA.length() のように使用します - 一方、length() を使用すると、長さを取得するために配列が完全にそれ自体を通過する必要があるため、アルゴリズムが O(k) ではなく O(n) を取るようになります。彼の主張は本当ですか？そうである場合、 O(k) になるようにコードをどのように変更すればよいですか? 助けてください、
助けていただければ幸いです。どうもありがとう。