2

これは宿題ではなく面接の質問です。

N 人の友達がゲームをしています。それぞれが自分の前に数字のリストを持っています。

N 人の友人のそれぞれが自分のリストから番号を選び、それをゲーム管理者に報告します。次に、ゲーム管理者は報告された数字を並べ替え、K 番目に大きい数字を叫びます。

ゲーム管理者が叫ぶ可能性のあるすべての数字を数えなければなりません。

たとえば、N = 3 で K = 3 の場合、3 人の友人のリストは2 5 3、8 1 6、7 4 9です。可能な値は であるため、出力は 6 です4 5 6 7 8 9。

この問題に対してまともなアルゴリズムを提案できる人はいますか? 私がやっていることは、各リストから 1 つの数値を取得してすべての可能な順列を作成し、結果を並べ替えて k 番目に大きいものを出力することです。しかし、それには時間がかかりすぎます。

4

2 に答える 2

6

結果に数値が存在するかどうかを知るには、上に数値があるかどうか、下に数値があるかどうかをリストごとに知る必要があります。上と下の両方の数字があるリストは、自分に合った数字を選択できるので問題ありません。問題は、上に数字のみ、または下に数字のみがあるリストです。最初のものは最大で NK でなければならず、2 番目のものは最大で K でなければなりません。これが当てはまらない場合、番号を選択することはできません。これが当てはまる場合は、上と下の両方の番号があるリストでいつでも番号を選択して、番号が選択されるようにすることができます。

これは線形時間でチェックできます。または、リストを最初にソートすると、全体的な複雑さが O(n.log(n)) になります。ここで、n は合計の数値です。並べ替えを行わないと、複雑さが n² になります。

リストを使用した例では：

{2 5 3}, {8 1 6}, {7 4 9}

2-最大の数を探しているとしましょう。番号ごとに、管理者が叫ぶことができるかどうかを尋ねます。それらのそれぞれについて、他のリストに下の数字と上の数字の両方があるかどうかを調べます。それらのいくつかをさらに見てみましょう

  • 5 の場合: 他の両方のリストの上下に数字があります。したがって、「5」は管理者が叫ぶことができます。

  • 「2」の場合: 2 番目のリストの上下に数字があるので、このリストの上または下の数字を自由に選択できます。ただし、3 番目のリストには上記の数字しかないため、このリストで選択された数字は常に大きくなります。2 番目のリストの下の数字を自由に選択できるため、「2」は 2 番目に大きい数字になります。

  • "1" の場合: 2 番目のリストの上には数字しかないため、"1" は常に最小の要素になります。

  • "9" の場合: これは逆で、常に最大です。

于 2012-10-01T07:51:11.867 に答える
6

各セットから最小の数を取ります。これらのうち K 番目に大きいものを見つけます。これは、結果に含まれる最小の数値です。同様に、結果の最大数を見つけます。2 つの間の各数値が結果に含まれていることを証明します。

于 2012-10-01T07:56:47.890 に答える