The Celebrity Problem

Q: Ünlü problemi için zaman karmaşıklığı nedir?

Eleme çözümleri O(n) zamanda çalışır: n-1 arama adayı bulur ve en fazla 2(n-1) kontrol işlemi adayı doğrular. İki işaretçili sürüm O(1) ek alan, yığın sürümü ise O(n) alan kullanır. Her kişiyi tanıma göre kontrol etmek O(n²) maliyetlidir.

Q: Birden fazla ünlü olabilir mi?

Hayır. İki kişi de ünlü olsaydı, her ikisi de herkes tarafından tanınırdı; dolayısıyla birbirlerini tanırlardı. Ancak bir ünlü kimseyi tanımaz, bu nedenle bir partide en fazla bir ünlü olabilir.

Q: Ünlü problemi grafiklerle nasıl ilişkilidir?

Matris, yönlü bir grafın komşuluk matrisidir: i düğümünden j düğümüne bir kenar olması, i düğümünün j düğümünü tanıdığı anlamına gelir. Bir ünlü, çıkış derecesi 0 ve giriş derecesi n-1 olan, evrensel bir yutak düğümdür. Dereceleri saymak tüm matrisi okumayı gerektirirken eleme, yutağı yalnızca O(n) hücreyi okuyarak bulur.

OrtaYığın İki işaretçi Graflar

+10

Bir partide 0 ile n-1 arasında numaralandırılmış n kişi var. matrix[i][j] değerinin, i kişisi j kişisini tanıyorsa 1, tanımıyorsa 0 olduğu n × n boyutunda bir matris veriliyor. Tanışıklık tek yönlüdür: i, j'yi tanırken j, i'yi tanımıyor olabilir.

Ünlü, diğer herkesin tanıdığı ancak hiç kimseyi tanımayan kişidir. Ünlünün numarasını döndürün; ünlü yoksa -1 döndürün.

Fonksiyon

findCelebrity(matrix: integer-2d-array) → integer

matrixinteger-2d-array: kimin kimi tanıdığı: i satırı, j sütunu, kişi i, kişi j'yi tanıyorsa 1'dir
Döndürürinteger: ünlünün numarası, yoksa -1

Kısıtlar

2 ≤ n ≤ 150, burada n satır ve sütun sayısıdır
matrix[i][j] değeri 0 veya 1'dir
matrix[i][i] = 0 her kişi için

Örnekler

Girdi: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Çıktı: 1
Açıklama: 1. satırın tamamı sıfırlardan oluşuyor, yani 1. kişi kimseyi tanımıyor. 1. sütunda 0. ve 2. satırlarda 1 var, yani diğer iki kişi de 1. kişiyi tanıyor. 1. kişi ünlüdür.

Ek soru

Her aramanın sormanız gereken bir soru olduğunu varsayın. En kötü durumda kaç soru sormanız gerekir ve 3(n-1) değerinin altına inebilir misiniz?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her kişiyi tanıma tanımına göre test etmek yaklaşık 2n² arama gerektirir. Bir hücre matrix[a][b] her zaman a ve b'den birini eler; bu nedenle n-1 arama tek bir adayı bırakır. Adayın satırı ve sütununda yapılacak tek bir tarama, onun ünlü kişi olup olmadığını belirler.

Her kişiyi kontrol et

Sezgi

c kişisi, c satırında hiç 1 yoksa (hiç kimseyi tanımıyorsa) ve kendi satırı dışındaki her satırda c sütununda 1 varsa (herkes onu tanıyorsa) ünlüdür. Bu tanımı sırayla her kişi için sınayın ve koşulu sağlayan ilk kişiyi döndürün.

Her kişi için en fazla 2(n-1) sorgu gerekir; toplamda yaklaşık 2n²: n = 150 için yaklaşık 45.000 sorgu.

Algoritma

0'dan n-1'e kadar her kişi c için diğer tüm kişilere bakın.
matrix[c][other] 1 ise veya matrix[other][c] 0 ise c ünlü değildir: sonraki kişiye geçin.
Başka hiç kimse c'yi eleyemezse c'yi döndürün.
Her kişi başarısız olursa -1 döndürün.

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

Bir yığın kullanarak ele

Sezgi

matrix[a][b] 1 ise a birini tanır ve ünlü kişi olamaz. 0 ise a, b'yi tanımaz; dolayısıyla b ünlü kişi olamaz. Her iki durumda da tek bir sorgu bir kişiyi kesin olarak eler. Herkesi bir yığına koy, ikişer kişi çıkar, sorgula ve hâlâ olası olan kişiyi geri koy: n-1 turdan sonra geriye bir kişi kalır.

Bu kişi bir adaydır, yanıt değil. Eleme, başka hiç kimsenin ünlü kişi olamayacağını gösterir; ancak hayatta kalan kişinin satırını ve sütununu hiçbir zaman kontrol etmez. Üçüncü örnekte hayatta kalan kişi 2'dir ve 3. kişiyi tanır; bu nedenle kontrol -1 döndürür. Kontrol için 2(n-1) ek sorgu gerekir; toplamda O(n) olur.

Algoritma

Her kişiyi bir yığına ekle.
Yığında birden fazla kişi olduğu sürece a ve b'yi çıkar.
a, b'yi tanıyorsa b'yi tekrar ekle; aksi hâlde a'yı tekrar ekle.
Son kişiyi aday olarak al. Bu kişi herhangi birini tanıyorsa veya herhangi biri onu tanımıyorsa -1 döndür.
Aksi hâlde adayı döndür.

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

İki işaretçi, sonra doğrula

Sezgi

Yığın yalnızca henüz elenmemiş kişileri tutar ve sıraları önemli değildir. Onu iki işaretçiyle değiştirin: ilk kişide a, son kişide b; a ile b arasındaki aralığın dışında kalan herkes zaten elenmiştir. a, b'yi tanıyorsa a elenir; aksi hâlde b elenir. İşaretçiler buluştuğunda, gösterdikleri kişi adaydır.

İlk örnekte matrix[0][2] 0'dır, bu yüzden 2. kişi elenir; ardından matrix[0][1] 1'dir, bu yüzden 0. kişi elenir. İşaretçiler, kontrolü geçen 1. kişide buluşur. Bu, n-1 arama ve en fazla 2(n-1) arama daha demektir; ek bellek kullanımı iki tamsayıdır.

Algoritma

a = 0 ve b = n-1 olarak ayarla.
a < b olduğu sürece: matrix[a][b] 1 ise a'yı 1 artır; aksi hâlde b'yi 1 azalt.
Aday a'dır. Diğer herkes için adayın o kişiyi tanımadığını ve o kişinin adayı tanıdığını kontrol et.
Tüm kontroller sağlanıyorsa adayı, aksi hâlde -1 değerini döndür.

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

Tuzaklar ve uç durumlar

Hayatta kalanı kontrol etmeden döndürmek. [[0, 1], [1, 0]] içinde hayatta kalan, birbirini tanıyan iki kişiden biridir ve yanıt -1'dir.
Yalnızca bir tarafı kontrol etmek. Üçüncü örnek yalnızca satırda başarısız olur: herkes 2. kişiyi tanır, ancak 2. kişi 3. kişiyi tanır.
Köşegeni saymak. matrix[c][c] değeri 0'dır; bu nedenle other == c koşulunu atlamayan bir sütun kontrolü, gerçek ünlülerin hepsini eler.
Hücreyi ters okumak. matrix[a][b] = 1, b'yi değil a'yı eler. Rolleri değiştirmek gerçek ünlüyü gözden çıkarır.
Lua veya R'de 1 tabanlı bir indeks döndürmek. Kişiler 0'dan başlayarak numaralandırılır; bu nedenle döndürmeden önce 1 çıkarın.

Sıkça sorulan sorular3

Ünlü problemi için zaman karmaşıklığı nedir?

Eleme çözümleri O(n) zamanda çalışır: n-1 arama adayı bulur ve en fazla 2(n-1) kontrol işlemi adayı doğrular. İki işaretçili sürüm O(1) ek alan, yığın sürümü ise O(n) alan kullanır. Her kişiyi tanıma göre kontrol etmek O(n²) maliyetlidir.

Birden fazla ünlü olabilir mi?

Hayır. İki kişi de ünlü olsaydı, her ikisi de herkes tarafından tanınırdı; dolayısıyla birbirlerini tanırlardı. Ancak bir ünlü kimseyi tanımaz, bu nedenle bir partide en fazla bir ünlü olabilir.

Ünlü problemi grafiklerle nasıl ilişkilidir?

Matris, yönlü bir grafın komşuluk matrisidir: i düğümünden j düğümüne bir kenar olması, i düğümünün j düğümünü tanıdığı anlamına gelir. Bir ünlü, çıkış derecesi 0 ve giriş derecesi n-1 olan, evrensel bir yutak düğümdür. Dereceleri saymak tüm matrisi okumayı gerektirirken eleme, yutağı yalnızca O(n) hücreyi okuyarak bulur.

def findCelebrity(matrix):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]

Beklenen Çıktı

The Celebrity Problem

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her kişiyi kontrol et

Bir yığın kullanarak ele

İki işaretçi, sonra doğrula

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler