The Celebrity Problem
يوجد n شخصًا في حفلة، مرقّمين من 0 إلى n-1. تحصل على مصفوفة n × n حيث تكون قيمة matrix[i][j] هي 1 إذا كان الشخص i يعرف الشخص j، و0 إذا لم يكن يعرفه. المعرفة أحادية الاتجاه: فقد يعرف i الشخص j بينما لا يعرف j الشخص i.
المشهور هو شخص يعرفه كل شخص آخر، ولا يعرف أي شخص. أعد رقم المشهور، أو -1 إذا لم يوجد مشهور.
الدالة
- matrixinteger-2d-array
- من يعرف من: تكون القيمة في الصف i، والعمود j هي 1 إذا كان الشخص i يعرف الشخص j
- تُرجع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 كله أصفار، لذا لا يعرف الشخص 1 أحدًا. يحتوي العمود 1 على الرقم 1 في الصفين 0 و2، لذا يعرف كلا الشخصين الآخرين الشخص 1. الشخص 1 هو المشهور.
- المدخلات
- matrix = [[0, 1], [1, 0]]
- المخرجات
- -1
- الشرح
- الشخص 0 يعرف الشخص 1، والشخص 1 يعرف الشخص 0. كلٌّ منهما يعرف شخصًا ما، لذا لا يمكن أن يكون أيٌّ منهما المشهور، والإجابة هي -1.
- المدخلات
- matrix = [[0, 0, 1, 0], [1, 0, 1, 1], [0, 0, 0, 1], [0, 1, 1, 0]]
- المخرجات
- -1
- الشرح
- يعرف الجميع الشخص 2، لكن الصف 2 يحتوي على 1 في العمود 3: الشخص 2 يعرف الشخص 3. وهذا يستبعد الشخص 2، ولا يوجد شخص آخر يعرفه الجميع، لذا فالإجابة هي -1.
سؤال إضافي
افترض أن كل عملية بحث هي سؤال عليك طرحه. ما أقل عدد من الأسئلة التي تحتاج إليها في أسوأ الحالات، وهل يمكنك النزول إلى أقل من 3(n-1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
قد تتطلب مقارنة كل شخص بالتعريف قراءة المصفوفة بأكملها. اختر شخصين
aوbوانظر إلى خلية واحدة،matrix[a][b]. أيًّا كان ما تشير إليه، فلا يمكن أن يكون أحد الشخصين هو المشهور. أيّهما في كل حالة؟إذا كان
aيعرفb، فإنaيعرف شخصًا ما ويُستبعَد. وإذا كانaلا يعرفb، فليس الجميع يعرفونb، لذا يُستبعَدb. كل عملية تحقّق تستبعد شخصًا واحدًا، لذا تتركn-1عملية تحقّق مرشحًا واحدًا.ضع مؤشرًا عند كل طرف،
a = 0وb = n-1. ما دامa < b، حرّكaإلى الأمام إذا كانaيعرفb، وإلا فحرّكbإلى الخلف. الناجي مجرد مرشح: تحقّق من صفّه وعموده قبل إرجاعه.
الحل
يتطلب اختبار كل شخص وفقًا للتعريف نحو 2n² عملية بحث. تستبعد خلية واحدة matrix[a][b] دائمًا أحد الشخصين a وb، لذا تترك n-1 عملية بحث مرشحًا واحدًا. ثم تحدد عملية مرور واحدة على صف المرشح وعموده ما إذا كان هو الشخصية المشهورة.
تحقّق من كل شخص
الفكرة
الشخص c هو المشهور عندما لا يحتوي الصف c على أي 1 (فهو لا يعرف أحدًا)، ويحتوي العمود c على 1 في كل صف باستثناء صفه (الجميع يعرفونه). اختبر هذا التعريف على كل شخص بالتتابع، وأعِد أول شخص يستوفيه.
يتطلب كل شخص ما يصل إلى 2(n-1) عملية بحث، أي نحو 2n² إجمالًا: عندما تكون n = 150، فهذا يعني نحو 45,000 عملية بحث.
الخوارزمية
- لكل شخص
cمن 0 إلىn-1، افحص كل شخص آخر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 هو المشهور. في كلتا الحالتين، تزيل عملية بحث واحدة شخصًا نهائيًا. ضع الجميع في مكدس، واسحب شخصين، واسأل، ثم أعد إلى المكدس الشخص الذي لا يزال من الممكن أن يكون المشهور: بعد n-1 جولات، يتبقى شخص واحد.
هذا الشخص مرشح، وليس إجابة. تُظهر عملية الاستبعاد أنه لا يمكن لأي شخص آخر أن يكون المشهور، لكنها لا تتحقق مطلقًا من صف الناجي وعموده. في المثال الثالث، الناجي هو الشخص 2، وهو يعرف الشخص 3، لذا يُرجع التحقق -1. يتطلب التحقق 2(n-1) عملية بحث إضافية، أي O(n) إجمالًا.
الخوارزمية
- ادفع كل شخص إلى المكدس.
- ما دام المكدس يحتوي على أكثر من شخص واحد، أخرج
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 cمؤشّران، ثم تحقّق
الفكرة
لا يحتفظ المكدس إلا بالأشخاص الذين لم يُستبعدوا بعد، ولا يهم ترتيبهم. استبدله بمؤشرين، a عند الشخص الأول وb عند الشخص الأخير: كل من يقع خارج النطاق من a إلى b مستبعَد بالفعل. إذا كان a يعرف b، فسيُستبعد a؛ وإلا فسيُستبعد b. عندما يلتقي المؤشران، يكون الشخص الذي يشيران إليه هو المرشح.
في المثال الأول، قيمة matrix[0][2] هي 0، لذا يُستبعد الشخص 2؛ ثم قيمة matrix[0][1] هي 1، لذا يُستبعد الشخص 0. يلتقي المؤشران عند الشخص 1، الذي يجتاز الفحص. وهذا يعني n-1 عملية وصول، بالإضافة إلى 2(n-1) على الأكثر، مع استخدام عددين صحيحين من الذاكرة الإضافية.
الخوارزمية
- عيّن
a = 0وb = n-1. - ما دام
a < b: إذا كانتmatrix[a][b]تساوي 1، فأضف 1 إلىa؛ وإلا فاطرح 1 منb. - المرشح هو
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]]يكون الناجي أحد شخصين يعرف أحدهما الآخر، والإجابة هي -1. - التحقق من جانب واحد فقط. يفشل المثال الثالث في الصف فقط: الجميع يعرفون الشخص 2، لكن الشخص 2 يعرف الشخص 3.
- احتساب القطر. قيمة
matrix[c][c]هي 0، لذا فإن التحقق من العمود الذي لا يتخطىother == cيرفض كل شخصية مشهورة حقيقية. - قراءة الخلية بالعكس.
matrix[a][b] = 1يستبعدa، لاb. وتبديل الدورين يؤدي إلى استبعاد الشخصية المشهورة الحقيقية. - إرجاع فهرس يبدأ من 1 في Lua أو R. يبدأ ترقيم الأشخاص من 0، لذا اطرح 1 قبل الإرجاع.
أسئلة شائعة3
ما هو التعقيد الزمني لمشكلة المشهور؟
تعمل حلول الإقصاء في زمن O(n): تحدد n-1 عملية بحث المرشح، وتتحقق منه بحد أقصى 2(n-1) عملية. تستخدم نسخة المؤشرين مساحة إضافية O(1)، بينما تستخدم نسخة المكدس O(n). أما التحقق من كل شخص وفقًا للتعريف فيكلف O(n²).
هل يمكن أن يكون هناك أكثر من شخصية مشهورة؟
لا. إذا كان شخصان من المشاهير، فسيكون كلٌّ منهما معروفًا لدى الجميع، وبالتالي سيعرف كلٌّ منهما الآخر. لكن المشهور لا يعرف أحدًا، لذا لا يمكن أن يكون في الحفلة أكثر من مشهور واحد.
ما علاقة مسألة المشاهير بالرسوم البيانية؟
المصفوفة هي مصفوفة المجاورة لرسم بياني موجّه: تعني الحافة من i إلى j أن i يعرف j. المشهور هو عقدة درجتها الصادرة 0 ودرجتها الواردة n-1، أي مصدر شامل. يتطلب حساب الدرجات قراءة المصفوفة بأكملها، بينما يعثر الاستبعاد على المصدر بعد قراءة O(n) خلية فقط.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def findCelebrity(matrix):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
الإخراج المتوقع
1