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

labuladong原创图论算法约 3503 字

Info

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

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

LeetCode	Difficulty
277. Find the Celebrity🔒	🟠

Prerequisites

Before reading this article, you need to learn:

Graph Structure Basics and General Implementation

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:

java 🟢

int findCelebrity(int[][] graph);

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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:

java 🟢

// 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
}

cpp 🤖

// 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
}

python 🤖

# 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

go 🤖

// 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
}

javascript 🤖

// 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:

java 🟢

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;
    }
}

cpp 🤖

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;
    }
};

python 🤖

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

go 🤖

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
    }
}

javascript 🤖

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:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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:

java 🟢

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;
    }
}

cpp 🤖

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;
    }
};

python 🤖

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

go 🤖

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
    }
}

javascript 🤖

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:

java 🟢

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;
    }
}

cpp 🤖

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;
    }
};

python 🤖

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

go 🤖

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
    }
}

javascript 🤖

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.

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

277. 搜寻名人 https://leetcode.cn/problems/find-the-celebrity

277. Find the Celebrity https://leetcode.com/problems/find-the-celebrity

Brute Force Solution

Optimized Solution

Final Solution