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

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

LeetCode 力扣 难度
277. Find the Celebrity🔒 277. 搜寻名人🔒 🟠

———–

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

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

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

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

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

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

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

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

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

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

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

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

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

给你输入一个大小为 n x n 的二维数组(邻接矩阵) graph 表示一幅有 n 个节点的图,每个人都是图中的一个节点,编号为 0n - 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 题「 搜寻名人」就是这个经典问题,不过并不是直接把邻接矩阵传给你,而是只告诉你总人数 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、名人不认识任何其他人。

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

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

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

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

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

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

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

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

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

对于情况一,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) 的空间复杂度。

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 充当一个队列,用于存储候选人集合,而这个优化解法利用 othercand 的交替变化,模拟了我们之前操作队列的过程,避免了使用额外的存储空间。

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


引用本文的文章

_____________

《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复关键词「进群」可加入算法群;回复「全家桶」可下载配套 PDF 和刷题全家桶

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