The Celebrity Problem
Có n người tại một bữa tiệc, được đánh số từ 0 đến n-1. Bạn nhận được một ma trận n × n, trong đó matrix[i][j] là 1 nếu người i biết người j và là 0 nếu không. Việc quen biết chỉ có một chiều: i có thể biết j trong khi j không biết i.
Người nổi tiếng là người được tất cả những người khác biết đến và không biết ai. Trả về số của người nổi tiếng, hoặc -1 nếu không có người nổi tiếng.
Hàm
- matrixinteger-2d-array
- ai biết ai: hàng i, cột j là 1 nếu người i biết người j
- Trả vềinteger
- số của người nổi tiếng, hoặc -1 nếu không có
Ràng buộc
2 ≤ n ≤ 150, trong đónlà số hàng và số cộtmatrix[i][j]là0hoặc1matrix[i][i] = 0cho mỗi người
Ví dụ
- Đầu vào
- matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
- Đầu ra
- 1
- Giải thích
- Hàng 1 toàn số 0, nên người số 1 không quen ai. Cột 1 có số 1 ở hàng 0 và hàng 2, nên cả hai người còn lại đều quen người số 1. Người số 1 là người nổi tiếng.
- Đầu vào
- matrix = [[0, 1], [1, 0]]
- Đầu ra
- -1
- Giải thích
- Người 0 quen người 1 và người 1 quen người 0. Cả hai đều quen một người, nên không ai trong số họ có thể là người nổi tiếng, và đáp án là -1.
- Đầu vào
- matrix = [[0, 0, 1, 0], [1, 0, 1, 1], [0, 0, 0, 1], [0, 1, 1, 0]]
- Đầu ra
- -1
- Giải thích
- Mọi người khác đều biết người số 2, nhưng hàng 2 có số 1 ở cột 3: người số 2 biết người số 3. Điều đó loại người số 2, và không ai khác được tất cả mọi người biết đến, nên đáp án là -1.
Câu hỏi mở rộng
Giả sử mỗi lần tra cứu là một câu hỏi bạn cần đặt ra. Trong trường hợp xấu nhất, bạn cần ít nhất bao nhiêu câu hỏi, và liệu bạn có thể giảm xuống dưới 3(n-1) không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Kiểm tra từng người theo định nghĩa có thể phải đọc toàn bộ ma trận. Chọn hai người
avàb, rồi xem một ô,matrix[a][b]. Dù ô đó ghi gì, một trong hai người không thể là người nổi tiếng. Trong mỗi trường hợp, đó là ai?Nếu
abiếtb, thìabiết một người nào đó và bị loại. Nếuakhông biếtb, thì không phải ai cũng biếtb, vì vậybbị loại. Mỗi lần tra cứu loại đi một người, nênn-1lần tra cứu sẽ còn lại một ứng viên.Đặt một con trỏ ở mỗi đầu,
a = 0vàb = n-1. Khia < b, tănganếuabiếtb, nếu không thì giảmb. Phần tử còn lại chỉ là ứng viên: hãy kiểm tra hàng và cột của nó trước khi return nó.
Lời giải
Kiểm tra từng người theo định nghĩa cần khoảng 2n² lần tra cứu. Mỗi ô matrix[a][b] luôn loại được một trong hai người a và b, nên n-1 lần tra cứu sẽ để lại một ứng viên duy nhất. Sau đó, kiểm tra một lượt hàng và cột của ứng viên sẽ xác định người đó có phải là người nổi tiếng hay không.
Kiểm tra từng người
Ý tưởng
Người c là người nổi tiếng nếu hàng c không có số 1 nào (họ không quen biết ai) và cột c có số 1 ở mọi hàng trừ hàng của chính họ (mọi người đều quen biết họ). Lần lượt kiểm tra định nghĩa đó với từng người và trả về người đầu tiên thỏa mãn.
Mỗi người cần tối đa 2(n-1) lần tra cứu, tổng cộng khoảng 2n²: n = 150 tương đương khoảng 45.000 lần tra cứu.
Thuật toán
- Với mỗi người
ctừ 0 đếnn-1, hãy xem xét từng người khácother. - Nếu
matrix[c][other]là 1 hoặcmatrix[other][c]là 0,ckhông phải người nổi tiếng: chuyển sang người tiếp theo. - Nếu không có người nào khác loại
c, hãy trả vềc. - Nếu tất cả mọi người đều không đạt, hãy trả về -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 -1Loại bỏ bằng ngăn xếp
Ý tưởng
Nếu matrix[a][b] là 1, a biết một người nào đó nên không thể là người nổi tiếng. Nếu giá trị là 0, a không biết b, nên b không thể là người nổi tiếng. Dù thế nào, một lần tra cứu cũng loại bỏ hẳn một người. Đưa mọi người vào một ngăn xếp, lấy ra hai người, hỏi rồi đưa người vẫn còn khả năng trở lại ngăn xếp: sau n-1 vòng, chỉ còn một người.
Người đó là ứng viên, chứ chưa phải đáp án. Việc loại trừ cho thấy không ai khác có thể là người nổi tiếng, nhưng không kiểm tra hàng và cột của người còn lại. Trong ví dụ thứ ba, người còn lại là người số 2, người này biết người số 3, nên bước kiểm tra trả về -1. Bước kiểm tra cần thêm 2(n-1) lần tra cứu, tổng cộng là O(n).
Thuật toán
- Đưa từng người vào một ngăn xếp.
- Trong khi ngăn xếp có nhiều hơn một người, lấy
avàbra. - Nếu
abiếtb, đưabtrở lại; nếu không, đưaatrở lại. - Lấy người cuối cùng làm ứng viên. Nếu người đó biết bất kỳ ai, hoặc có người không biết người đó, trả về -1.
- Nếu không, trả về ứng viên.
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 cHai con trỏ, sau đó xác minh
Ý tưởng
Ngăn xếp chỉ chứa những người chưa bị loại và thứ tự của họ không quan trọng. Thay ngăn xếp bằng hai con trỏ, a trỏ đến người đầu tiên và b trỏ đến người cuối cùng: những người nằm ngoài phạm vi từ a đến b đều đã bị loại. Nếu a biết b, thì a bị loại; nếu không, b bị loại. Khi hai con trỏ gặp nhau, người mà chúng đang trỏ đến là ứng viên.
Trong ví dụ đầu tiên, matrix[0][2] là 0, nên người thứ 2 bị loại; tiếp theo, matrix[0][1] là 1, nên người thứ 0 bị loại. Hai con trỏ gặp nhau tại người thứ 1, người này vượt qua bước kiểm tra. Cách này cần n-1 lần tra cứu cộng thêm tối đa 2(n-1), với bộ nhớ bổ sung là hai số nguyên.
Thuật toán
- Đặt
a = 0vàb = n-1. - Trong khi
a < b: nếumatrix[a][b]là 1, tăngathêm 1; nếu không, giảmbđi 1. - Người được chọn là
a. Với mỗi người khác, kiểm tra xem người được chọn không quen họ và họ biết người được chọn. - Trả về người được chọn nếu mọi điều kiện đều đúng, nếu không thì trả về -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
Lỗi thường gặp và trường hợp biên
- Trả về người còn lại mà không kiểm tra. Trong
[[0, 1], [1, 0]], người còn lại là một trong hai người quen nhau, nên đáp án là -1. - Chỉ kiểm tra một phía. Ví dụ thứ ba chỉ thất bại ở hàng: mọi người đều quen người thứ 2, nhưng người thứ 2 lại quen người thứ 3.
- Tính cả đường chéo.
matrix[c][c]là 0, vì vậy bước kiểm tra cột không bỏ quaother == csẽ loại mọi người nổi tiếng thực sự. - Đọc ngược ô.
matrix[a][b] = 1loạia, không phảib. Đổi vai trò sẽ loại bỏ người nổi tiếng thực sự. - Trả về chỉ số bắt đầu từ 1 trong Lua hoặc R. Mọi người được đánh số từ 0, vì vậy hãy trừ 1 trước khi trả về.
Câu hỏi thường gặp3
Độ phức tạp thời gian của bài toán người nổi tiếng là gì?
Các lời giải loại trừ chạy trong thời gian O(n): n-1 lần tra cứu tìm ra ứng viên và cần tối đa 2(n-1) lần kiểm tra ứng viên đó. Phiên bản hai con trỏ dùng thêm O(1) bộ nhớ, còn phiên bản dùng ngăn xếp dùng O(n). Kiểm tra từng người theo định nghĩa tốn O(n²).
Có thể có nhiều hơn một người nổi tiếng không?
Không. Nếu cả hai người đều là người nổi tiếng, ai cũng được mọi người biết đến, nên họ sẽ biết nhau. Nhưng người nổi tiếng không quen biết ai, vì vậy một bữa tiệc có nhiều nhất một người nổi tiếng.
Vấn đề người nổi tiếng liên quan đến đồ thị như thế nào?
Ma trận này là ma trận kề của một đồ thị có hướng: cạnh từ i đến j có nghĩa là i biết j. Người nổi tiếng là một nút có bậc ra bằng 0 và bậc vào là n-1, tức là một nút hút phổ quát. Đếm bậc sẽ đọc toàn bộ ma trận, còn phép loại trừ tìm ra nút hút sau khi chỉ đọc O(n) ô.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def findCelebrity(matrix):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
Đầu ra mong đợi
1