The Celebrity Problem
パーティーには、0からn-1まで番号が付けられたn人の人がいます。matrix[i][j]が、人物iが人物jを知っている場合は1、知らない場合は0となるn × n行列が与えられます。知り合いであることは一方通行の場合があります。つまり、iはjを知っていても、jはiを知らないことがあります。
セレブとは、他の全員から知られていて、誰のことも知らない人物です。セレブの番号を返し、セレブがいない場合は-1を返してください。
関数
- matrixinteger-2d-array
- 誰が誰を知っているか：人物 i が人物 j を知っている場合、行 i、列 j の値は 1
- 戻り値integer
- 有名人の番号、または存在しない場合は -1
制約
2 ≤ n ≤ 150。ここで、nは行数と列数です。matrix[i][j]は0または1matrix[i][i] = 0は各人について
例
- 入力
- matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
- 出力
- 1
- 説明
- 行 1 はすべて 0 なので、person 1 は誰も知りません。列 1 には行 0 と 2 に 1 があるので、ほかの 2 人はどちらも person 1 を知っています。person 1 が有名人です。
- 入力
- matrix = [[0, 1], [1, 0]]
- 出力
- -1
- 説明
- 人物 0 は人物 1 を知っており、人物 1 は人物 0 を知っています。2 人とも誰かを知っているため、どちらも有名人ではなく、答えは -1 です。
- 入力
- matrix = [[0, 0, 1, 0], [1, 0, 1, 1], [0, 0, 0, 1], [0, 1, 1, 0]]
- 出力
- -1
- 説明
- 他の人は全員人物2を知っていますが、2行目の3列目は1です。つまり、人物2は人物3を知っています。したがって人物2は候補から除外され、全員から知られている人は他にいないため、答えは-1です。
発展問題
各検索が、あなたが尋ねなければならない質問だとしましょう。最悪の場合、質問はいくつ必要でしょうか。また、3(n-1)未満にできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
定義に照らして全員を確認すると、行列全体を読み取ることになります。2人の人物
aとbを選び、1つのセルmatrix[a][b]を見てみましょう。そこに何が書かれていても、2人のうちどちらかは有名人ではありません。各場合、どちらでしょうか？aがbを知っているなら、aは誰かを知っているため候補から外れます。aがbを知らないなら、全員がbを知っているわけではないため、bは候補から外れます。1回の照会で1人を除外できるので、n-1回の照会で候補が1人残ります。両端にポインターを置きます。
a = 0とb = n-1です。a < bの間、aがbを知っている場合はaを前に進め、そうでなければbを後ろに戻します。残った人は候補にすぎません。返す前に、その人の行と列を確認してください。
解説
定義に照らして全員を調べるには、約 2n² 回の検索が必要です。1つのセル matrix[a][b] によって、a と b のどちらか一方が必ず候補から外れるため、n-1 回の検索で候補が1人に絞られます。その候補の行と列を1回ずつ調べれば、その人が有名人かどうかを判定できます。
すべての人を確認する
考え方
行 c に 1 がなく（誰のことも知らず）、自分以外のすべての行で列 c に 1 がある（全員がその人を知っている）場合、その人物 c は有名人です。この定義を順番に各人物について確認し、条件を満たす最初の人物を返します。
各人物につき最大 2(n-1) 回の照会が必要で、合計では約 2n² 回です。n = 150 の場合、約 45,000 回の照会になります。
アルゴリズム
- 0から
n-1までの各人cについて、他のすべての人otherを確認します。 matrix[c][other]が1、またはmatrix[other][c]が0の場合、cは有名人ではありません。次の人に進みます。- 他の人によって
cが候補から除外されなければ、cを返します。 - すべての人が条件を満たさない場合は、-1を返します。
def findCelebrity(matrix):
n = len(matrix)
for c in range(n):
is_celebrity = True
for other in range(n):
# c must know no one, and everyone else must know c.
if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
is_celebrity = False
break
if is_celebrity:
return c
return -1スタックを使って削除する
考え方
matrix[a][b]が1なら、aは誰かを知っているため、有名人にはなれません。0なら、aはbを知らないため、bは有名人にはなれません。どちらの場合も、1回の参照で1人を完全に候補から除外できます。全員をスタックに入れ、2人を取り出して質問し、まだ候補になり得る方を戻します。n-1回繰り返すと、1人が残ります。
その人は候補であって、答えではありません。候補の絞り込みによって、他の誰も有名人ではないと分かりますが、残った人の行と列は確認されません。3つ目の例では、人2が残りますが、その人は人3を知っているため、確認結果は-1になります。この確認にはさらに2(n-1)回の参照が必要で、合計ではO(n)です。
アルゴリズム
- すべての人をスタックに積みます。
- スタックに1人より多くの人がいる間、
aとbを取り出します。 aがbを知っている場合は、bをスタックに戻します。そうでなければ、aを戻します。- 最後に残った人を候補者とします。その人が誰かを知っている場合、または誰かがその人を知らない場合は、-1を返します。
- そうでなければ、候補者を返します。
def findCelebrity(matrix):
n = len(matrix)
candidates = list(range(n))
# Each question removes one person who cannot be the celebrity.
while len(candidates) > 1:
a = candidates.pop()
b = candidates.pop()
candidates.append(b if matrix[a][b] == 1 else a)
c = candidates[0]
# The survivor is only a candidate: check every other person.
for other in range(n):
if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
return -1
return c2つのポインターを使い、その後で検証する
考え方
スタックには、まだ候補から除外されていない人だけが入り、その順序は重要ではありません。これを2つのポインタに置き換えます。最初の人を指すaと最後の人を指すbです。aからbまでの範囲外の人は、すでに除外されています。aがbを知っていれば、aを除外します。そうでなければ、bを除外します。ポインタが一致したとき、その人が候補です。
最初の例では、matrix[0][2]は0なので、人2が除外されます。次に、matrix[0][1]は1なので、人0が除外されます。ポインタは人1の位置で一致し、その人はチェックに合格します。参照回数はn-1回に最大で2(n-1)回が加わり、追加メモリは整数2個分です。
アルゴリズム
a = 0、b = n-1を設定します。a < bの間、matrix[a][b]が1ならaに1を加え、それ以外の場合はbから1を引きます。- 候補者は
aです。他のすべての人について、候補者がその人を知らず、その人が候補者を知っていることを確認します。 - すべての確認に合格した場合は候補者を返し、そうでなければ-1を返します。
def findCelebrity(matrix):
n = len(matrix)
a, b = 0, n - 1
# Each question rules out one of the two people.
while a < b:
if matrix[a][b] == 1:
a += 1 # a knows someone, so a is not the celebrity
else:
b -= 1 # a does not know b, so b is not the celebrity
# a is the only person left who could be the celebrity: check it.
for other in range(n):
if other != a and (matrix[a][other] == 1 or matrix[other][a] == 0):
return -1
return a
落とし穴と境界ケース
- 確認せずに候補者を返すこと。
[[0, 1], [1, 0]]では、候補者は互いを知っている2人のうちの1人なので、答えは-1です。 - 片側だけを確認すること。3つ目の例は、行だけを確認すると失敗します。全員が人物2を知っていますが、人物2は人物3を知っています。
- 対角線を数えること。
matrix[c][c]は0なので、other == cをスキップしない列のチェックでは、本物の有名人は全員除外されます。 - セルの値を逆に読むこと。
matrix[a][b] = 1によって候補から外れるのはaであり、bではありません。役割を入れ替えると、本物の有名人を除外してしまいます。 - LuaまたはRで1始まりのインデックスを返すこと。人物には0から番号が振られているため、返す前に1を引いてください。
よくある質問3
セレブリティ問題の時間計算量はどのくらいですか？
消去法による解法は O(n) 時間で実行されます。n-1 回の検索で候補者を見つけ、最大で 2(n-1) 回の確認でその候補者を検証します。2ポインター版は追加領域に O(1)、スタック版は O(n) を使用します。定義に照らして全員を確認すると、O(n²) のコストがかかります。
有名人は複数いることがありますか？
いいえ。2人がどちらも有名人なら、それぞれが皆に知られているため、互いのことを知っているはずです。しかし、有名人は誰のことも知らないので、パーティーに有名人は多くても1人です。
有名人問題はグラフとどのように関係していますか？
この行列は有向グラフの隣接行列です。i から j への辺は、i が j を知っていることを意味します。セレブリティとは、出次数が 0 で入次数が n-1 のノード、つまり普遍的なシンクです。次数を数えるには行列全体を読み取りますが、消去法なら O(n) 個のセルを読むだけでシンクを見つけられます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def findCelebrity(matrix):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
期待される出力
1