997. 找到小镇的法官

🟢 🔖 图 数组 哈希表 🔗 力扣open in new window LeetCodeopen in new window

题目

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.

Return the label of the town judge if the town judge exists and can be identified, or return-1 otherwise.

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Constraints:

1 <= n <= 1000
0 <= trust.length <= 10^4
trust[i].length == 2
All the pairs of trust are unique.
ai != bi
1 <= ai, bi <= n

题目大意

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

小镇法官不会信任任何人。
每个人（除了小镇法官）都信任这位小镇法官。
只有一个人同时满足属性 1 和属性 2 。

给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

示例 1：

输入： n = 2, trust = [[1,2]]
输出： 2

示例 2：

输入： n = 3, trust = [[1,3],[2,3]]
输出： 3

示例 3：

输入： n = 3, trust = [[1,3],[2,3],[3,1]]
输出： -1

提示：

1 <= n <= 1000
0 <= trust.length <= 10^4
trust[i].length == 2
trust 中的所有trust[i] = [ai, bi] 互不相同
ai != bi
1 <= ai, bi <= n

解题思路

初始化数据结构：
- 创建一个 judge 数组，长度为 n + 1，用来记录每个节点（对应每个人）被信任的次数。judge[i] 表示第 i 个人被信任的次数。
- 使用一个 believer 集合来记录所有信任了其他人的人。即，信任关系中的每个 a 都加入到 believer 中。
处理信任关系：
- 遍历 trust 数组，针对每个信任关系 [a, b]：
  - 将 judge[b] 加 1，表示 b 被信任了一次。
  - 将 a 加入到 believer 集合中，表示 a 信任了别人。
寻找法官：
- 法官是一个特殊的个体，他被 n - 1 个人信任，并且他自己不信任任何人。因此，遍历 judge 数组，找到被信任次数等于 n - 1 且不在 believer 集合中的人。
返回结果：
- 如果找到符合条件的人，返回其编号（即法官编号）；如果没有找到符合条件的人，则返回 -1。

复杂度分析

时间复杂度：O(t + n)
- 遍历 trust 数组的时间复杂度是 O(T)，其中 t 是 trust 数组的长度。
- 遍历 judge 数组的时间复杂度是 O(n)，其中 n 是人数。
空间复杂度：O(n)
- judge 数组的大小为 n + 1，占用 O(n) 的空间。
- believer 集合最多包含 n 个人，占用 O(n) 的空间。

代码

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function (n, trust) {
	let judge = new Array(n + 1).fill(0),
		believer = new Set();

	// 处理信任关系
	for (let [a, b] of trust) {
		judge[b]++;
		believer.add(a);
	}

	// 寻找法官
	for (let i = 1; i <= n; i++) {
		if (judge[i] == n - 1 && !believer.has(i)) {
			return i;
		}
	}
	return -1;
};

997. 找到小镇的法官

# 997. 找到小镇的法官

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

997. 找到小镇的法官

题目

题目大意

解题思路

复杂度分析

代码

相关题目