LeetCode 277. 搜寻名人

Categories:

题目描述
思路分析
1. 解法一：候选人淘汰（推荐）
相似题目

题目描述

✅ 277. 搜寻名人

思路分析

解法一：候选人淘汰（推荐）

核心思路：

先用一遍扫描筛选出可能的名人候选。

再验证候选是否满足“所有人认识他，他不认识任何人”。

若满足返回候选，否则返回 -1。

复杂度分析：

时间复杂度：O(n)，其中 n 表示人数。

空间复杂度：O(1)。

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int cand = 0;
        for (int i = 1; i < n; i++) {
            if (knows(cand, i)) {
                cand = i;
            }
        }

        for (int i = 0; i < n; i++) {
            if (i == cand) {
                continue;
            }
            if (knows(cand, i) || !knows(i, cand)) {
                return -1;
            }
        }

        return cand;
    }
}

func findCelebrity(n int) int {
	cand := 0
	for i := 1; i < n; i++ {
		if knows(cand, i) {
			cand = i
		}
	}

	for i := 0; i < n; i++ {
		if i == cand {
			continue
		}
		if knows(cand, i) || !knows(i, cand) {
			return -1
		}
	}

	return cand
}

相似题目

题目	难度	考察点
277. 搜寻名人	中等	候选人淘汰
287. 寻找重复数	中等	候选思想
11. 盛最多水的容器	中等	双指针
169. 多数元素	简单	投票法
229. 多数元素 II	中等	投票法

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/43694293