# 众里寻他千百度：名流问题

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

277. Find the Celebrity🔒 | 🟠 |

Prerequisites

Before reading this article, you need to learn:

Today, we'll discuss the classic "Celebrity Problem":

You are given the social relationships of `n`

people (you know whether any two people know each other), and you need to find the "celebrity" among them.

A "celebrity" meets two conditions:

- All other people know the "celebrity."
- The "celebrity" does not know any other person.

This is an algorithm problem related to graphs. Social relationships can essentially be abstracted into a graph.

If we consider each person as a node in the graph and the "knowing" relationship as a directed edge between nodes, then the celebrity is a special node in this graph:

**This node has no directed edges pointing to other nodes; and all other nodes have a directed edge pointing to this node**.

In more technical terms, the out-degree of the celebrity node is 0, and the in-degree is `n - 1`

.

So, how are the social relationships of these `n`

people represented?

As mentioned in the previous article Graph Theory Basics, there are two ways to store a graph: adjacency list and adjacency matrix. The main advantage of an adjacency list is saving storage space; the main advantage of an adjacency matrix is the ability to quickly determine whether two nodes are adjacent.

For the celebrity problem, we often need to check if two people know each other, i.e., if two nodes are adjacent. Therefore, we can use an adjacency matrix to represent the social relationships between people.

Thus, the celebrity problem can be described in algorithmic terms as follows:

You are given an `n x n`

2D array (adjacency matrix) `graph`

representing a graph with `n`

nodes. Each person is a node in the graph, numbered from `0`

to `n - 1`

.

If `graph[i][j] == 1`

, it means person `i`

knows person `j`

. If `graph[i][j] == 0`

, it means person `i`

does not know person `j`

.

Given this graph representing relationships between people, your task is to determine if there is a "celebrity" among these `n`

people.

If a celebrity exists, the algorithm should return their number; if not, it should return -1.

The function signature is as follows:

`int findCelebrity(int[][] graph);`

`int findCelebrity(vector<vector<int>>& graph);`

`def findCelebrity(graph: List[List[int]]) -> int:`

`func findCelebrity(graph [][]int) int {}`

`var findCelebrity = function(graph) { }`

For example, the input adjacency matrix looks like this:

In this case, the algorithm should return 2.

LeetCode problem #277 "Find the Celebrity" is based on this classic problem. However, instead of directly giving you the adjacency matrix, it only tells you the total number of people `n`

and provides an API `knows`

to query the social relationships between people:

```
// can be called directly, returns whether i knows j
boolean knows(int i, int j);
// please implement: return the number of the "celebrity"
int findCelebrity(int n) {
// todo
}
```

```
// can be called directly, returns whether i knows j
bool knows(int i, int j);
// please implement: return the number of the "celebrity"
int findCelebrity(int n) {
// todo
}
```

```
# Can be called directly, returns whether i knows j
def knows(i: int, j: int) -> bool:
pass
# Please implement: return the number of the 'celebrity'
def findCelebrity(n: int) -> int:
# todo
```

```
// can be called directly, returns whether i knows j
func knows(i int, j int) bool {}
// please implement: return the number of the "celebrity"
func findCelebrity(n int) int {
// todo
}
```

```
// can be called directly, returns whether i knows j
var knows = function(i, j) {};
// please implement: return the number of the 'celebrity'
var findCelebrity = function(n) {
// todo
};
```

Clearly, the `knows`

API essentially accesses an adjacency matrix. For simplicity, we will discuss this classic problem following the format of LeetCode problems.

## Brute Force Solution

We can quickly come up with a simple and straightforward algorithm:

```
class Solution extends Relation {
public int findCelebrity(int n) {
for (int cand = 0; cand < n; cand++) {
int other;
for (other = 0; other < n; other++) {
if (cand == other) continue;
// ensure that everyone else knows cand, and cand does not know anyone else
// otherwise, cand cannot be the celebrity
if (knows(cand, other) || !knows(other, cand)) {
break;
}
}
if (other == n) {
// found the celebrity
return cand;
}
}
// no one fits the characteristics of a celebrity
return -1;
}
}
```

```
class Solution {
public:
int findCelebrity(int n) {
for (int cand = 0; cand < n; cand++) {
int other;
for (other = 0; other < n; other++) {
if (cand == other) continue;
// ensure everyone else knows cand, and cand does not know anyone else
// otherwise, cand cannot be the celebrity
if (knows(cand, other) || !knows(other, cand)) {
break;
}
}
if (other == n) {
// found the celebrity
return cand;
}
}
// no one matches the characteristics of a celebrity
return -1;
}
};
```

```
class Solution:
def findCelebrity(self, n: int) -> int:
for cand in range(n):
other = 0
# ensure everyone else knows cand, and cand does not know anyone else
# otherwise, cand cannot be the celebrity
while other < n:
if cand == other:
other += 1
continue
if knows(cand, other) or not knows(other, cand):
break
other += 1
if other == n:
# found the celebrity
return cand
# no one fits the characteristics of a celebrity
return -1
```

```
func solution(knows func(a int, b int) bool) func(n int) int {
return func(n int) int {
for cand := 0; cand < n; cand++ {
var other int
for other = 0; other < n; other++ {
if cand == other {
continue
}
// ensure everyone else knows cand, and cand does not know anyone else
// otherwise cand cannot be the celebrity
if knows(cand, other) || !knows(other, cand) {
break
}
}
if other == n {
// found the celebrity
return cand
}
}
// no one has the characteristics of a celebrity
return -1
}
}
```

```
var solution = function(knows) {
return function(n) {
for (let cand = 0; cand < n; cand++) {
let other;
for (other = 0; other < n; other++) {
if (cand === other) {
continue;
}
// ensure everyone else knows cand, and cand does not know anyone else
// otherwise cand cannot be the celebrity
if (knows(cand, other) || !knows(other, cand)) {
break;
}
}
if (other === n) {
// found the celebrity
return cand;
}
}
// no one matches the celebrity characteristics
return -1;
};
};
```

`cand`

is short for "candidate." Our brute-force algorithm starts from the beginning, treating everyone as a candidate and checking if they meet the "celebrity" criteria.

As mentioned earlier, the `knows`

function essentially accesses a two-dimensional adjacency matrix, with a time complexity of O(1) per call. Therefore, the overall worst-case time complexity of this brute-force solution is O(N^2).

Is there a smarter way to optimize the time complexity? Actually, there is room for optimization. Think about where the most time-consuming part is.

For each candidate `cand`

, we use an inner for loop to determine if `cand`

meets the "celebrity" criteria.

This inner for loop seems inefficient. While checking if someone is a "celebrity" requires a for loop, determining that someone is not a "celebrity" doesn't need to be so complicated.

**Because the definition of a "celebrity" ensures uniqueness, we can use the process of elimination to first exclude those who are obviously not "celebrities," thereby avoiding nested for loops and reducing the time complexity**.

## Optimized Solution

Let me reiterate the definition of a "celebrity":

- Everyone else knows the celebrity.
- The celebrity knows no one else.

This definition is intriguing because it ensures that there can be at most one celebrity in a group.

This is easy to understand. If there were two celebrities, these definitions would contradict each other.

**In other words, by observing the relationship between any two candidates, I can definitely determine that one of them is not a celebrity and eliminate them**.

Whether the other candidate is a celebrity cannot be determined by just looking at the relationship between two people, but that's not important. What matters is that we eliminate a candidate who is definitely not a celebrity, thereby narrowing down the possibilities.

This is the core of the optimization and can be a bit tricky to grasp, so let's discuss why observing the relationship between any two candidates allows us to eliminate one.

Think about it, what can the relationship between two people be like?

There are only four possibilities: you know me and I don't know you, I know you and you don't know me, we know each other, or we don't know each other.

If we compare people to nodes, with red directed edges representing "not knowing" and green directed edges representing "knowing," then the relationship between two people can be one of the following four scenarios:

Let's assume the two people are labeled `cand`

and `other`

, and then we analyze each scenario to see how we can eliminate one person.

For scenario one, `cand`

knows `other`

, so `cand`

cannot be a celebrity and is eliminated. Because a celebrity cannot know anyone else.

For scenario two, `other`

knows `cand`

, so `other`

cannot be a celebrity and is eliminated.

For scenario three, they know each other, so neither can be a celebrity, and we can eliminate either one.

For scenario four, they don't know each other, so neither can be a celebrity, and we can eliminate either one. Because a celebrity should be known by everyone else.

In summary, by observing the relationship between any two people, we can at least determine that one of them is not a celebrity. The above scenario judgments can be represented by the following code:

```
if (knows(cand, other) || !knows(other, cand)) {
// cand cannot be a celebrity
} else {
// other cannot be a celebrity
}
```

```
if (knows(cand, other) || !knows(other, cand)) {
// cand cannot be a celebrity
}
else {
// other cannot be a celebrity
}
```

```
if knows(cand, other) or not knows(other, cand):
# cand cannot be the celebrity
else:
# other cannot be the celebrity
```

```
if knows(cand, other) || !knows(other, cand) {
// cand cannot be the celebrity
} else {
// other cannot be the celebrity
}
```

```
if (knows(cand, other) || !knows(other, cand)) {
// cand cannot be a celebrity
} else {
// other cannot be a celebrity
}
```

If you can understand this characteristic, writing an optimized solution becomes simple.

**We can continuously select two candidates and eliminate one until only one candidate remains. At that point, we use a for loop to determine if this candidate is truly a "celebrity".**

Here is the complete code for this approach:

```
class Solution extends Relation {
public int findCelebrity(int n) {
if (n == 1) return 0;
// put all candidates into the queue
LinkedList<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
q.addLast(i);
}
// keep eliminating until only one candidate is left
while (q.size() >= 2) {
// each time take out two candidates and eliminate one
int cand = q.removeFirst();
int other = q.removeFirst();
if (knows(cand, other) || !knows(other, cand)) {
// cand cannot be the celebrity, eliminate and let other rejoin the queue
q.addFirst(other);
} else {
// other cannot be the celebrity, eliminate and let cand rejoin the queue
q.addFirst(cand);
}
}
// now there is only one candidate left, determine if he is really the celebrity
int cand = q.removeFirst();
for (int other = 0; other < n; other++) {
if (other == cand) {
continue;
}
// ensure that everyone else knows cand, and cand does not know anyone else
if (!knows(other, cand) || knows(cand, other)) {
return -1;
}
}
// cand is the celebrity
return cand;
}
}
```

```
class Solution {
public:
int findCelebrity(int n) {
if (n == 1) return 0;
// put all candidates into the queue
queue<int> q;
for (int i = 0; i < n; i++) {
q.push(i);
}
// keep eliminating until only one candidate is left
while (q.size() >= 2) {
// each time take out two candidates and eliminate one
int cand = q.front();
q.pop();
int other = q.front();
q.pop();
if (knows(cand, other) || !knows(other, cand)) {
// cand cannot be the celebrity, eliminate and let other rejoin the queue
q.push(other);
} else {
// other cannot be the celebrity, eliminate and let cand rejoin the queue
q.push(cand);
}
}
// now that only one candidate is left, determine if he is really the celebrity
int cand = q.front();
for (int other = 0; other < n; other++) {
if (other == cand) {
continue;
}
// ensure that everyone else knows cand, and cand does not know anyone else
if (!knows(other, cand) || knows(cand, other)) {
return -1;
}
}
// cand is the celebrity
return cand;
}
};
```

```
class Solution:
def findCelebrity(self, n: int) -> int:
if n == 1:
return 0
# put all candidates into the queue
q = collections.deque(range(n))
# keep eliminating until only one candidate is left
while len(q) >= 2:
# each time take out two candidates and eliminate one
cand = q.popleft()
other = q.popleft()
if knows(cand, other) or not knows(other, cand):
# cand cannot be the celebrity, eliminate and let other rejoin the queue
q.appendleft(other)
else:
# other cannot be the celebrity, eliminate and let cand rejoin the queue
q.appendleft(cand)
# now only one candidate is left, determine if he is really the celebrity
cand = q.popleft()
for other in range(n):
if other == cand:
continue
# ensure everyone else knows cand, and cand does not know any other person
if not knows(other, cand) or knows(cand, other):
return -1
# cand is the celebrity
return cand
```

```
func solution(knows func(a int, b int) bool) func(n int) int {
return func(n int) int {
if n == 1 {
return 0
}
// put all candidates into the queue
q := make([]int, n)
for i := 0; i < n; i++ {
q[i] = i
}
// keep eliminating until there is only one candidate left in the loop
for len(q) >= 2 {
// each time take out two candidates and eliminate one
cand := q[0]
q = q[1:]
other := q[0]
q = q[1:]
if knows(cand, other) || !knows(other, cand) {
// cand cannot be the celebrity, eliminate and let other rejoin the queue
q = append([]int{other}, q...)
} else {
// other cannot be the celebrity, eliminate and let cand rejoin the queue
q = append([]int{cand}, q...)
}
}
// now that there is only one candidate left, determine if he is really a celebrity
cand := q[0]
for other := 0; other < n; other++ {
if other == cand {
continue
}
// ensure that everyone else knows cand, and cand does not know any other person
if !knows(other, cand) || knows(cand, other) {
return -1
}
}
// cand is the celebrity
return cand
}
}
```

```
var solution = function(knows) {
return function(n) {
if (n === 1) {
return 0;
}
// put all candidates into the queue
let q = Array.from({ length: n }, (_, i) => i);
// keep eliminating until only one candidate is left
while (q.length >= 2) {
// each time take out two candidates and eliminate one
let cand = q.shift();
let other = q.shift();
if (knows(cand, other) || !knows(other, cand)) {
// cand cannot be the celebrity, eliminate and let other rejoin the queue
q.unshift(other);
} else {
// other cannot be the celebrity, eliminate and let cand rejoin the queue
q.unshift(cand);
}
}
// now there is only one candidate left, determine if he is really a celebrity
let cand = q.shift();
for (let other = 0; other < n; other++) {
if (other === cand) {
continue;
}
// make sure everyone else knows cand, and cand does not know anyone else
if (!knows(other, cand) || knows(cand, other)) {
return -1;
}
}
// cand is the celebrity
return cand;
};
};
```

This algorithm avoids nested for loops, reducing the time complexity to O(N). However, it introduces a queue to store the set of candidates, using O(N) space complexity.

注

The role of `LinkedList`

is simply to act as a container to hold the candidates. Each time, two candidates are selected for comparison and elimination. The specific choice of which two candidates to select does not matter. In other words, the order in which candidates are enqueued is irrelevant. We use `addFirst`

just for the convenience of future optimizations. You could use `addLast`

instead, and the result would be the same.

Can we further optimize to reduce the space complexity as well?

## Final Solution

If you understand the optimization method described above, you can actually solve this problem without using extra space. The code is as follows:

```
class Solution extends Relation {
public int findCelebrity(int n) {
int cand = 0;
for (int other = 1; other < n; other++) {
if (!knows(other, cand) || knows(cand, other)) {
// cand cannot be a celebrity, eliminate
// assume other is a celebrity
cand = other;
} else {
// other cannot be a celebrity, eliminate
// do nothing, continue to assume cand is a celebrity
}
}
// now cand is the last one remaining after elimination, but it's not guaranteed to be a celebrity
for (int other = 0; other < n; other++) {
if (cand == other) continue;
// need to ensure everyone else knows cand, and cand does not know any other person
if (!knows(other, cand) || knows(cand, other)) {
return -1;
}
}
return cand;
}
}
```

```
class Solution {
public:
int findCelebrity(int n) {
int cand = 0;
for (int other = 1; other < n; other++) {
if (!knows(other, cand) || knows(cand, other)) {
// cand cannot be the celebrity, eliminate
// assume other is the celebrity
cand = other;
} else {
// other cannot be the celebrity, eliminate
// do nothing, continue to assume cand is the celebrity
}
}
// now cand is the last remaining candidate, but it's not guaranteed to be the celebrity
for (int other = 0; other < n; other++) {
if (cand == other) continue;
// need to ensure everyone else knows cand, and cand does not know any other person
if (!knows(other, cand) || knows(cand, other)) {
return -1;
}
}
return cand;
}
};
```

```
class Solution:
def findCelebrity(self, n: int) -> int:
cand = 0
for other in range(1, n):
if not knows(other, cand) or knows(cand, other):
# cand can't be the celebrity, eliminate
# assume other is the celebrity
cand = other
else:
# other can't be the celebrity, eliminate
# do nothing, continue to assume cand is the celebrity
pass
# now cand is the last one remaining after elimination, but it's not guaranteed to be the celebrity
for other in range(n):
if cand == other:
continue
# need to ensure everyone else knows cand, and cand doesn't know any other person
if not knows(other, cand) or knows(cand, other):
return -1
return cand
```

```
func solution(knows func(a int, b int) bool) func(n int) int {
return func(n int) int {
cand := 0
for other := 1; other < n; other++ {
if !knows(other, cand) || knows(cand, other) {
// cand cannot be the celebrity, eliminate
// assume other is the celebrity
cand = other
} else {
// other cannot be the celebrity, eliminate
// do nothing, continue to assume cand is the celebrity
}
}
// now cand is the last one remaining after elimination, but it's not guaranteed to be the celebrity
for other := 0; other < n; other++ {
if cand == other {
continue
}
// need to ensure everyone else knows cand, and cand does not know any other person
if !knows(other, cand) || knows(cand, other) {
return -1
}
}
return cand
}
}
```

```
var solution = function(knows) {
return function(n) {
let cand = 0;
for (let other = 1; other < n; other++) {
if (!knows(other, cand) || knows(cand, other)) {
// cand cannot be the celebrity, eliminate
// assume other is the celebrity
cand = other;
} else {
// other cannot be the celebrity, eliminate
// do nothing, continue to assume cand is the celebrity
}
}
// now cand is the last remaining after elimination, but it's not guaranteed to be the celebrity
for (let other = 0; other < n; other++) {
if (cand === other) {
continue;
}
// need to ensure everyone else knows cand, and cand does not know anyone else
if (!knows(other, cand) || knows(cand, other)) {
return -1;
}
}
return cand;
};
};
```

Our previous solution used a `LinkedList`

to act as a queue for storing the set of candidates. This optimized solution uses the alternating changes between `other`

and `cand`

to simulate our previous queue operations, avoiding the use of extra storage space.

Now, the solution to the celebrity problem has a time complexity of O(N) and a space complexity of O(1), making it the optimal solution.