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

labuladong约 6403 字大约 21 分钟图论算法

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

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

LeetCode	力扣	难度
277. Find the Celebrityopen in new window🔒	277. 搜寻名人open in new window🔒	🟠

今天来讨论经典的「名流问题」：

给你 n 个人的社交关系（你知道任意两个人之间是否认识），然后请你找出这些人中的「名人」。

所谓「名人」有两个条件：

1、所有其他人都认识「名人」。

2、「名人」不认识任何其他人。

这是一个图相关的算法问题，社交关系嘛，本质上就可以抽象成一幅图。

如果把每个人看做图中的节点，「认识」这种关系看做是节点之间的有向边，那么名人就是这幅图中一个特殊的节点：

这个节点没有一条指向其他节点的有向边；且其他所有节点都有一条指向这个节点的有向边。

或者说的专业一点，名人节点的出度为 0，入度为 n - 1。

那么，这 n 个人的社交关系是如何表示的呢？

前文图论算法基础说过，图有两种存储形式，一种是邻接表，一种是邻接矩阵，邻接表的主要优势是节约存储空间；邻接矩阵的主要优势是可以迅速判断两个节点是否相邻。

对于名人问题，显然会经常需要判断两个人之间是否认识，也就是两个节点是否相邻，所以我们可以用邻接矩阵来表示人和人之间的社交关系。

那么，把名流问题描述成算法的形式就是这样的：

给你输入一个大小为 n x n 的二维数组（邻接矩阵） graph 表示一幅有 n 个节点的图，每个人都是图中的一个节点，编号为 0 到 n - 1。

如果 graph[i][j] == 1 代表第 i 个人认识第 j 个人，如果 graph[i][j] == 0 代表第 i 个人不认识第 j 个人。

有了这幅图表示人与人之间的关系，请你计算，这 n 个人中，是否存在「名人」？

如果存在，算法返回这个名人的编号，如果不存在，算法返回 -1。

函数签名如下：

int findCelebrity(int[][] graph);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

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

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

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

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func findCelebrity(graph [][]int) int

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var findCelebrity = function(graph) { 
}

比如输入的邻接矩阵长这样：

那么算法应该返回 2。

力扣第 277 题「搜寻名人open in new window」就是这个经典问题，不过并不是直接把邻接矩阵传给你，而是只告诉你总人数 n，同时提供一个 API knows 来查询人和人之间的社交关系：

// 可以直接调用，能够返回 i 是否认识 j
boolean knows(int i, int j);

// 请你实现：返回「名人」的编号
int findCelebrity(int n) {
    // todo
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 可以直接调用，能够返回 i 是否认识 j
bool knows(int i, int j);

// 请你实现：返回「名人」的编号
int findCelebrity(int n) {
    // todo
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 可以直接调用，能够返回 i 是否认识 j
def knows(i: int, j: int) -> bool:

# 请你实现：返回「名人」的编号
def findCelebrity(n: int) -> int:
    # todo

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 可以直接调用，能够返回 i 是否认识 j
func knows(i int, j int) bool {
    // todo
}

// 请你实现：返回「名人」的编号
func findCelebrity(n int) int {
    // todo
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 可以直接调用，能够返回 i 是否认识 j
var knows = function(i, j) {};

// 请你实现：返回「名人」的编号
var findCelebrity = function(n) {
    // todo
};

很明显，knows API 本质上还是在访问邻接矩阵。为了简单起见，我们后面就按力扣的题目形式来探讨一下这个经典问题。

暴力解法

我们拍拍脑袋就能写出一个简单粗暴的算法：

int findCelebrity(int n) {
    for (int cand = 0; cand < n; cand++) {
        int other;
        for (other = 0; other < n; other++) {
            if (cand == other) continue;
            // 保证其他人都认识 cand，且 cand 不认识任何其他人
            // 否则 cand 就不可能是名人
            if (knows(cand, other) || !knows(other, cand)) {
                break;
            }
        }
        if (other == n) {
            // 找到名人
            return cand;
        }
    }
    // 没有一个人符合名人特性
    return -1;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int findCelebrity(int n) {
    for (int cand = 0; cand < n; cand++) {
        int other;
        for (other = 0; other < n; other++) {
            if (cand == other) continue;
            // 保证其他人都认识 cand，且 cand 不认识任何其他人
            // 否则 cand 就不可能是名人
            if (knows(cand, other) || !knows(other, cand)) {
                break;
            }
        }
        if (other == n) {
            // 找到名人
            return cand;
        }
    }
    // 没有一个人符合名人特性
    return -1;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def findCelebrity(n: int) -> int:
    for cand in range(n):
        other = 0
        # 保证其他人都认识 cand，且 cand 不认识任何其他人
        # 否则 cand 就不可能是名人
        while other < n:
            if cand == other:
                other += 1
                continue
            if knows(cand, other) or not knows(other, cand):
                break
            other += 1
        if other == n:
            # 找到名人
            return cand
    # 没有一个人符合名人特性
    return -1

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func findCelebrity(n int) int {
    for cand := 0; cand < n; cand++ {
        var other int
        for other = 0; other < n; other++ {
            if cand == other {
                continue
            }
            // 保证其他人都认识 cand，且 cand 不认识任何其他人
            // 否则 cand 就不可能是名人
            if knows(cand, other) || !knows(other, cand) {
                break
            }
        }
        if other == n {
            // 找到名人
            return cand
        }
    }
    // 没有一个人符合名人特性
    return -1
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

function findCelebrity(n) {
    for (var cand = 0; cand < n; cand++) {
        // 遍历每个人，判断该人是否为名人
        var other;
        for (other = 0; other < n; other++) {
            if (cand == other) continue;
            // 判断 cand 是否认识 other
            // 或者 other 不认识 cand，若成立则跳出循环
            if (knows(cand, other) || !knows(other, cand)) {
                break;
            }
        }
        // 若 other 遍历完所有人都认识 cand （cand 除外），则 cand 是名人
        if (other == n) {
            return cand;
        }
    }
    // 遍历完所有人，没有一个人符合名人特性
    return -1;
}

cand 是候选人（candidate）的缩写，我们的暴力算法就是从头开始穷举，把每个人都视为候选人，判断是否符合「名人」的条件。

刚才也说了，knows 函数底层就是在访问一个二维的邻接矩阵，一次调用的时间复杂度是 O(1)，所以这个暴力解法整体的最坏时间复杂度是 O(N^2)。

那么，是否有其他高明的办法来优化时间复杂度呢？其实是有优化空间的，你想想，我们现在最耗时的地方在哪里？

对于每一个候选人 cand，我们都要用一个内层 for 循环去判断这个 cand 到底符不符合「名人」的条件。

这个内层 for 循环看起来就蠢，虽然判断一个人「是名人」必须用一个 for 循环，但判断一个人「不是名人」就不用这么麻烦了。

因为「名人」的定义保证了「名人」的唯一性，所以我们可以利用排除法，先排除那些显然不是「名人」的人，从而避免 for 循环的嵌套，降低时间复杂度。

优化解法

我再重复一遍所谓「名人」的定义：

1、所有其他人都认识名人。

2、名人不认识任何其他人。

这个定义就很有意思，它保证了人群中最多有一个名人。

这很好理解，如果有两个人同时是名人，那么这两条定义就自相矛盾了。

换句话说，只要观察任意两个候选人的关系，我一定能确定其中的一个人不是名人，把他排除。

至于另一个候选人是不是名人，只看两个人的关系肯定是不能确定的，但这不重要，重要的是排除掉一个必然不是名人的候选人，缩小了包围圈。

这是优化的核心，也是比较难理解的，所以我们先来说说为什么观察任意两个候选人的关系，就能排除掉一个。

你想想，两个人之间的关系可能是什么样的？

无非就是四种：你认识我我不认识你，我认识你你不认识我，咱俩互相认识，咱两互相不认识。

如果把人比作节点，红色的有向边表示不认识，绿色的有向边表示认识，那么两个人的关系无非是如下四种情况：

不妨认为这两个人的编号分别是 cand 和 other，然后我们逐一分析每种情况，看看怎么排除掉一个人。

对于情况一，cand 认识 other，所以 cand 肯定不是名人，排除。因为名人不可能认识别人。

对于情况二，other 认识 cand，所以 other 肯定不是名人，排除。

对于情况三，他俩互相认识，肯定都不是名人，可以随便排除一个。

对于情况四，他俩互不认识，肯定都不是名人，可以随便排除一个。因为名人应该被所有其他人认识。

综上，只要观察任意两个之间的关系，就至少能确定一个人不是名人，上述情况判断可以用如下代码表示：

if (knows(cand, other) || !knows(other, cand)) {
    // cand 不可能是名人
} else {
    // other 不可能是名人
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

if (knows(cand, other) || !knows(other, cand)) {
    // cand 不可能是名人
}
else {
    // other 不可能是名人
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

if knows(cand, other) or not knows(other, cand):
    # cand 不可能是名人
else:
    # other 不可能是名人

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

if knows(cand, other) || !knows(other, cand) {
    // cand 不可能是名人
} else {
    // other 不可能是名人
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var isCelebrity;
if (knows(cand, other) || !knows(other, cand)) {
    // cand 不可能是名人
    isCelebrity = false;
} else {
    // other 不可能是名人
    isCelebrity = true;
}

如果能够理解这一个特点，那么写出优化解法就简单了。

我们可以不断从候选人中选两个出来，然后排除掉一个，直到最后只剩下一个候选人，这时候再使用一个 for 循环判断这个候选人是否是货真价实的「名人」。

这个思路的完整代码如下：

int findCelebrity(int n) {
    if (n == 1) return 0;
    // 将所有候选人装进队列
    LinkedList<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        q.addLast(i);
    }
    // 一直排除，直到只剩下一个候选人停止循环
    while (q.size() >= 2) {
        // 每次取出两个候选人，排除一个
        int cand = q.removeFirst();
        int other = q.removeFirst();
        if (knows(cand, other) || !knows(other, cand)) {
            // cand 不可能是名人，排除，让 other 归队
            q.addFirst(other);
        } else {
            // other 不可能是名人，排除，让 cand 归队
            q.addFirst(cand);
        }
    }

    // 现在排除得只剩一个候选人，判断他是否真的是名人
    int cand = q.removeFirst();
    for (int other = 0; other < n; other++) {
        if (other == cand) {
            continue;
        }
        // 保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }
    // cand 是名人
    return cand;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int findCelebrity(int n) {
    if (n == 1) return 0;
    // 将所有候选人装进队列
    queue<int> q;
    for (int i = 0; i < n; i++) {
        q.push(i);
    }
    // 一直排除，直到只剩下一个候选人停止循环
    while (q.size() >= 2) {
        // 每次取出两个候选人，排除一个
        int cand = q.front(); q.pop();
        int other = q.front(); q.pop();
        if (knows(cand, other) || !knows(other, cand)) {
            // cand 不可能是名人，排除，让 other 归队
            q.push(other);
        } else {
            // other 不可能是名人，排除，让 cand 归队
            q.push(cand);
        }
    }

    // 现在排除得只剩一个候选人，判断他是否真的是名人
    int cand = q.front(); q.pop();
    for (int other = 0; other < n; other++) {
        if (other == cand) {
            continue;
        }
        // 保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }
    // cand 是名人
    return cand;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def findCelebrity(n: int) -> int:
    if n == 1:
        return 0
    # 将所有候选人装进队列
    q = []
    for i in range(n):
        q.append(i)
    # 一直排除，直到只剩下一个候选人停止循环
    while len(q) >= 2:
        # 每次取出两个候选人，排除一个
        cand = q.pop(0)
        other = q.pop(0)
        if knows(cand, other) or not knows(other, cand):
            # cand 不可能是名人，排除，让 other 归队
            q.insert(0, other)
        else:
            # other 不可能是名人，排除，让 cand 归队
            q.insert(0, cand)

    # 现在排除得只剩一个候选人，判断他是否真的是名人
    cand = q.pop(0)
    for other in range(n):
        if other == cand:
            continue
        # 保证其他人都认识 cand，且 cand 不认识任何其他人
        if not knows(other, cand) or knows(cand, other):
            return -1
    # cand 是名人
    return cand

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func findCelebrity(n int) int {
    if n == 1 {
        return 0
    }
    // 将所有候选人装进队列
    q := make([]int, n)
    for i := 0; i < n; i++ {
        q[i] = i
    }

    // 一直排除，直到只剩下一个候选人停止循环
    for len(q) >= 2 {
        // 每次取出两个候选人，排除一个
        cand := q[0]
        q = q[1:]
        other := q[0]
        q = q[1:]
        if knows(cand, other) || !knows(other, cand) {
            // cand 不可能是名人，排除，让 other 归队
            q = append([]int{other}, q...)
        } else {
            // other 不可能是名人，排除，让 cand 归队
            q = append([]int{cand}, q...)
        }
    }

    // 现在排除得只剩一个候选人，判断他是否真的是名人
    cand := q[0]
    for other := 0; other < n; other++ {
        if other == cand {
            continue
        }
        // 保证其他人都认识 cand，且 cand 不认识任何其他人
        if !knows(other, cand) || knows(cand, other) {
            return -1
        }
    }
    // cand 是名人
    return cand
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 找到名人的编号
var findCelebrity = function(n) {
    if (n === 1) return 0;
    // 将所有候选人装进队列
    let q = [];
    for (let i = 0; i < n; i++) {
        q.push(i);
    }
    // 一直排除，直到只剩下一个候选人停止循环
    while (q.length >= 2) {
        // 每次取出两个候选人，排除一个
        let cand = q.shift();
        let other = q.shift();
        if (knows(cand, other) || !knows(other, cand)) {
            // cand 不可能是名人，排除，让 other 归队
            q.unshift(other);
        } else {
            // other 不可能是名人，排除，让 cand 归队
            q.unshift(cand);
        }
    }

    // 现在排除得只剩一个候选人，判断他是否真的是名人
    let cand = q.shift();
    for (let other = 0; other < n; other++) {
        if (other === cand) {
            continue;
        }
        // 保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }
    // cand 是名人
    return cand;
};

这个算法避免了嵌套 for 循环，时间复杂度降为 O(N) 了，不过引入了一个队列来存储候选人集合，使用了 O(N) 的空间复杂度。

Note

LinkedList 的作用只是充当一个容器把候选人装起来，每次找出两个进行比较和淘汰，但至于具体找出哪两个，都是无所谓的，也就是说候选人归队的顺序无所谓，我们用的是 addFirst 只是方便后续的优化，你完全可以用 addLast，结果都是一样的。

是否可以进一步优化，把空间复杂度也优化掉？

最终解法

如果你能够理解上面的优化解法，其实可以不需要额外的空间解决这个问题，代码如下：

int findCelebrity(int n) {
    // 先假设 cand 是名人
    int cand = 0;
    for (int other = 1; other < n; other++) {
        if (!knows(other, cand) || knows(cand, other)) {
            // cand 不可能是名人，排除
            // 假设 other 是名人
            cand = other;
        } else {
            // other 不可能是名人，排除
            // 什么都不用做，继续假设 cand 是名人
        }
    }

    // 现在的 cand 是排除的最后结果，但不能保证一定是名人
    for (int other = 0; other < n; other++) {
        if (cand == other) continue;
        // 需要保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }

    return cand;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int findCelebrity(int n) {
    // 先假设 cand 是名人
    int cand = 0;
    for (int other = 1; other < n; other++) {
        if (!knows(other, cand) || knows(cand, other)) {
            // cand 不可能是名人，排除
            // 假设 other 是名人
            cand = other;
        } else {
            // other 不可能是名人，排除
            // 什么都不用做，继续假设 cand 是名人
        }
    }

    // 现在的 cand 是排除的最后结果，但不能保证一定是名人
    for (int other = 0; other < n; other++) {
        if (cand == other) continue;
        // 需要保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }

    return cand;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def findCelebrity(n: int) -> int:
    # 先假设 cand 是名人
    cand = 0
    for other in range(1, n):
        if not knows(other, cand) or knows(cand, other):
            # cand 不可能是名人，排除
            # 假设 other 是名人
            cand = other
        else:
            # other 不可能是名人，排除
            # 什么都不用做，继续假设 cand 是名人
            pass
    # 现在的 cand 是排除的最后结果，但不能保证一定是名人
    for other in range(n):
        if cand == other:
            continue
        # 需要保证其他人都认识 cand，且 cand 不认识任何其他人
        if not knows(other, cand) or knows(cand, other):
            return -1
    return cand

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func findCelebrity(n int) int {
    // 先假设 cand 是名人
    cand := 0
    for other := 1; other < n; other++ {
        if !knows(other, cand) || knows(cand, other) {
            // cand 不可能是名人，排除
            // 假设 other 是名人
            cand = other
        } else {
            // other 不可能是名人，排除
            // 什么都不用做，继续假设 cand 是名人
        }
    }

    // 现在的 cand 是排除的最后结果，但不能保证一定是名人
    for other := 0; other < n; other++ {
        if cand == other {
            continue
        }
        // 需要保证其他人都认识 cand，且 cand 不认识任何其他人
        if !knows(other, cand) || knows(cand, other) {
            return -1
        }
    }

    return cand
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 找到名人
var findCelebrity = function(n) {
    // 先假设 cand 是名人
    let cand = 0;
    for (let other = 1; other < n; other++) {
        if (!knows(other, cand) || knows(cand, other)) {
            // cand 不可能是名人，排除
            // 假设 other 是名人
            cand = other;
        } else {
            // other 不可能是名人，排除
            // 什么都不用做，继续假设 cand 是名人
        }
    }

    // 现在的 cand 是排除的最后结果，但不能保证一定是名人
    for (let other = 0; other < n; other++) {
        if (cand === other) continue;
        // 需要保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }

    return cand;
}

我们之前的解法用到了 LinkedList 充当一个队列，用于存储候选人集合，而这个优化解法利用 other 和 cand 的交替变化，模拟了我们之前操作队列的过程，避免了使用额外的存储空间。

现在，解决名人问题的解法时间复杂度为 O(N)，空间复杂度为 O(1)，已经是最优解法了。

引用本文的文章

二分图判定算法

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 暴力解法

# 优化解法

# 最终解法

暴力解法

优化解法

最终解法