The Celebrity Problem

Q: Apa kompleksitas waktu dari masalah selebritas?

Solusi eliminasi berjalan dalam waktu O(n) : n-1 pencarian menemukan kandidat dan paling banyak 2(n-1) pemeriksaan untuk memeriksanya. Versi two-pointer menggunakan ruang ekstra O(1) , sedangkan versi stack menggunakan O(n) . Memeriksa setiap orang berdasarkan definisi membutuhkan biaya O(n²) .

Q: Apakah bisa ada lebih dari satu selebritas?

Tidak. Jika dua orang sama-sama selebritas, semua orang akan mengenal masing-masing, jadi keduanya akan saling mengenal. Namun, seorang selebritas tidak mengenal siapa pun, jadi sebuah pesta paling banyak memiliki satu selebritas.

Q: Bagaimana masalah selebritas berkaitan dengan graf?

Matriks ini adalah matriks ketetanggaan dari graf berarah: sisi dari i ke j berarti i mengenal j . Selebritas adalah simpul dengan derajat keluar 0 dan derajat masuk n-1 , yaitu simpul tujuan universal. Menghitung derajat berarti membaca seluruh matriks, sedangkan eliminasi menemukan simpul tujuan setelah hanya membaca O(n) sel.

SedangStack Two pointers Graf

+10

Ada n orang di sebuah pesta, bernomor dari 0 hingga n-1. Kamu mendapatkan matriks n × n, dengan matrix[i][j] bernilai 1 jika orang i mengenal orang j dan 0 jika tidak. Saling mengenal tidak harus timbal balik: i bisa mengenal j, sementara j tidak mengenal i.

Selebritas adalah orang yang dikenal oleh semua orang lain dan tidak mengenal siapa pun. Kembalikan nomor selebritas tersebut, atau -1 jika tidak ada selebritas.

Fungsi

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

matrixinteger-2d-array: siapa mengenal siapa: baris i, kolom j bernilai 1 jika orang i mengenal orang j
Mengembalikaninteger: nomor selebritas tersebut, atau -1 jika tidak ada

Batasan

2 ≤ n ≤ 150, dengan n adalah jumlah baris dan kolom
matrix[i][j] bernilai 0 atau 1
matrix[i][i] = 0 untuk setiap orang

Contoh

Input: matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Output: 1
Penjelasan: Baris 1 semuanya berisi nol, jadi orang 1 tidak mengenal siapa pun. Kolom 1 berisi angka 1 pada baris 0 dan 2, jadi kedua orang lainnya mengenal orang 1. Orang 1 adalah selebritas.

Pertanyaan lanjutan

Misalkan setiap pencarian adalah pertanyaan yang harus kamu ajukan. Berapa sedikit pertanyaan yang kamu perlukan dalam kasus terburuk, dan bisakah kamu mendapat kurang dari 3(n-1)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Menguji setiap orang berdasarkan definisi membutuhkan sekitar 2n² pencarian. Satu sel matrix[a][b] selalu menyingkirkan salah satu dari a dan b, jadi n-1 pencarian menyisakan satu kandidat. Satu kali pemeriksaan pada baris dan kolom kandidat kemudian menentukan apakah dia selebritas.

Periksa setiap orang

Intuisi

Orang c adalah selebritas jika baris c tidak memiliki angka 1 (dia tidak mengenal siapa pun) dan kolom c memiliki angka 1 di setiap baris selain barisnya sendiri (semua orang mengenalnya). Uji definisi itu untuk setiap orang secara bergiliran, lalu kembalikan orang pertama yang memenuhi syarat.

Setiap orang memerlukan hingga 2(n-1) pencarian, totalnya sekitar 2n²: n = 150 berarti sekitar 45.000 pencarian.

Algoritma

Untuk setiap orang c dari 0 hingga n-1, periksa setiap orang lainnya, other.
Jika matrix[c][other] bernilai 1, atau matrix[other][c] bernilai 0, c bukan selebritas: lanjutkan ke orang berikutnya.
Jika tidak ada orang lain yang menggugurkan c, kembalikan c.
Jika semua orang gagal, kembalikan -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

Hapus dengan stack

Intuisi

Jika matrix[a][b] bernilai 1, a mengenal seseorang dan tidak mungkin menjadi selebritas. Jika nilainya 0, a tidak mengenal b, jadi b tidak mungkin menjadi selebritas. Bagaimanapun, satu kali pencarian mengeliminasi satu orang selamanya. Masukkan semua orang ke dalam tumpukan, keluarkan dua orang, ajukan pertanyaan, lalu masukkan kembali orang yang masih mungkin: setelah n-1 putaran, tersisa satu orang.

Orang itu adalah kandidat, bukan jawaban. Eliminasi menunjukkan bahwa tidak ada orang lain yang bisa menjadi selebritas, tetapi tidak pernah memeriksa baris dan kolom orang yang tersisa. Dalam contoh ketiga, orang yang tersisa adalah orang 2, yang mengenal orang 3, jadi pemeriksaan menghasilkan -1. Pemeriksaan ini membutuhkan 2(n-1) pencarian tambahan, sehingga totalnya O(n).

Algoritma

Masukkan setiap orang ke dalam stack.
Selama stack berisi lebih dari satu orang, keluarkan a dan b.
Jika a mengenal b, masukkan kembali b; jika tidak, masukkan kembali a.
Ambil orang terakhir sebagai kandidat. Jika ia mengenal siapa pun, atau siapa pun tidak mengenalnya, kembalikan -1.
Jika tidak, kembalikan kandidat.

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

Dua pointer, lalu verifikasi

Intuisi

Tumpukan hanya menyimpan orang-orang yang belum disingkirkan, dan urutannya tidak penting. Ganti dengan dua penunjuk, a pada orang pertama dan b pada orang terakhir: semua orang di luar rentang a hingga b sudah disingkirkan. Jika a mengenal b, a disingkirkan; jika tidak, b disingkirkan. Saat kedua penunjuk bertemu, orang yang ditunjuk adalah kandidatnya.

Dalam contoh pertama, matrix[0][2] bernilai 0, jadi orang 2 disingkirkan; lalu matrix[0][1] bernilai 1, jadi orang 0 disingkirkan. Kedua penunjuk bertemu pada orang 1, yang lolos pemeriksaan. Itu berarti n-1 akses ditambah paling banyak 2(n-1), dengan tambahan memori sebesar dua bilangan bulat.

Algoritma

Tetapkan a = 0 dan b = n-1.
Selama a < b: jika matrix[a][b] bernilai 1, tambahkan 1 ke a; jika tidak, kurangi 1 dari b.
Kandidatnya adalah a. Untuk setiap orang lainnya, periksa bahwa kandidat tidak mengenal mereka dan mereka mengenal kandidat.
Kembalikan kandidat jika semua pemeriksaan terpenuhi, jika tidak, -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

Jebakan dan kasus tepi

Mengembalikan orang yang tersisa tanpa memeriksanya. Dalam [[0, 1], [1, 0]], orang yang tersisa adalah salah satu dari dua orang yang saling mengenal, dan jawabannya adalah -1.
Hanya memeriksa satu sisi. Contoh ketiga hanya gagal pada baris: semua orang mengenal orang 2, tetapi orang 2 mengenal orang 3.
Menghitung diagonal. matrix[c][c] bernilai 0, jadi pemeriksaan kolom yang tidak melewati other == c akan menolak setiap selebritas yang sebenarnya.
Membaca sel secara terbalik. matrix[a][b] = 1 mencoret a, bukan b. Menukar perannya akan membuang selebritas yang sebenarnya.
Mengembalikan indeks berbasis 1 di Lua atau R. Nomor orang dimulai dari 0, jadi kurangi 1 sebelum mengembalikannya.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari masalah selebritas?

Solusi eliminasi berjalan dalam waktu O(n): n-1 pencarian menemukan kandidat dan paling banyak 2(n-1) pemeriksaan untuk memeriksanya. Versi two-pointer menggunakan ruang ekstra O(1), sedangkan versi stack menggunakan O(n). Memeriksa setiap orang berdasarkan definisi membutuhkan biaya O(n²).

Apakah bisa ada lebih dari satu selebritas?

Tidak. Jika dua orang sama-sama selebritas, semua orang akan mengenal masing-masing, jadi keduanya akan saling mengenal. Namun, seorang selebritas tidak mengenal siapa pun, jadi sebuah pesta paling banyak memiliki satu selebritas.

Bagaimana masalah selebritas berkaitan dengan graf?

Matriks ini adalah matriks ketetanggaan dari graf berarah: sisi dari i ke j berarti i mengenal j. Selebritas adalah simpul dengan derajat keluar 0 dan derajat masuk n-1, yaitu simpul tujuan universal. Menghitung derajat berarti membaca seluruh matriks, sedangkan eliminasi menemukan simpul tujuan setelah hanya membaca O(n) sel.

def findCelebrity(matrix):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

The Celebrity Problem

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Periksa setiap orang

Hapus dengan stack

Dua pointer, lalu verifikasi

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa