facebook - N個の与えられたセットのそれぞれからK番目に大きい数を与える例を説明してください?

Question

今日はFacebook プログラミング チャレンジを解いてみました。私が受けた課題は、ここで見つけることができる「バーの問題」でした。チャレンジ中の私の問題は、彼らが提供した最初の例を理解することでした.

この問題は次のように要約できます。

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

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

ゲーム管理者が叫ぶ可能性のあるすべての数字を数えたいとします。

その時点まで、私は問題を理解したと思っていましたが、次の例を示しました。

与えられたサンプル例では、最初のテストケースで N = 3 および K = 3 です。1 人目のリストは {2 5 3}、2 人目は {8 1 6}、3 人目は {7 4 9} です。この場合、{4, 5, 6, 7, 8, 9} のすべての数字が、選択された 3 番目に大きい数字になる可能性があります。

だから私の質問は：

7、8、9 が 3 番目に大きい選択数になるのはなぜですか?

私の意見では、数字 {1, 2, 3, 4, 5} のみが 3 番目に大きい数字になる可能性がありますが、アルゴリズムを誤解している可能性があります。

Answer 1

質問は 3 番目に小さいことを意味する必要があります。

セットの配列 S_1、S_2...S_N を指定して、1 つを選択し、指定された要素を選択します。すべての集合の最大要素と最小要素の両方がわかっていると仮定し、集合を 3 つのグループに分けます。すべての要素が e より大きいもの、すべての要素が e 未満のもの、e より大きい要素と小さい要素の両方があるもの。

N 個のセットのセットで、最小の k 個のセットの場合、すべての要素が e より小さいセットは k-1 個を超えてはならず、すべての要素が e より大きい Nk 個のセットを超えてはなりません。これらの 2 つの条件が成立する場合、i は、e よりも大きい集合と小さい集合を取り、e が選択されるように並べることができます。