Skip to content

Latest commit

 

History

History
179 lines (139 loc) · 4.19 KB

README.md

File metadata and controls

179 lines (139 loc) · 4.19 KB

997. 找到小镇的法官

English Version

题目描述

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

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

  1. 小镇法官不会信任任何人。
  2. 每个人（除了小镇法官）都信任这位小镇法官。
  3. 只有一个人同时满足属性 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 <= 104
  • trust[i].length == 2
  • trust 中的所有trust[i] = [ai, bi] 互不相同
  • ai != bi
  • 1 <= ai, bi <= n

解法

创建长度为 1001 的计数器 c1[i]、c2[i]，其中 c1[i] 表示 i 信任的人数，c2[i] 表示信任 i 的人数。

遍历 trust 列表，统计人数，最后再遍历计数器，若存在 c1[i] == 0 && c2[i] == n - 1，说明存在法官，直接返回 i。否则遍历结束返回 -1。

Python3

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        N = 1001
        c1, c2 = [0] * N, [0] * N
        for a, b in trust:
            c1[a] += 1
            c2[b] += 1
        for i in range(1, N):
            if c1[i] == 0 and c2[i] == n - 1:
                return i
        return -1

Java

class Solution {
    public int findJudge(int n, int[][] trust) {
        int N = 1001;
        int[] c1 = new int[N];
        int[] c2 = new int[N];
        for (int[] e : trust) {
            ++c1[e[0]];
            ++c2[e[1]];
        }
        for (int i = 1; i < N; ++i) {
            if (c1[i] == 0 && c2[i] == n - 1) {
                return i;
            }
        }
        return -1;
    }
}

TypeScript

function findJudge(n: number, trust: number[][]): number {
    let candidates = new Array(n).fill(0);
    for (let [a, b] of trust) {
        candidates[a - 1] = -1;
        if (candidates[b - 1] >= 0) {
            candidates[b - 1]++;
        }
    }

    for (let i = 0; i < n; i++) {
        if (candidates[i] == n - 1) {
            return i + 1;
        }
    }
    return -1;
}

C++

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        int N = 1001;
        vector<int> c1(N);
        vector<int> c2(N);
        for (auto& e : trust) {
            ++c1[e[0]];
            ++c2[e[1]];
        }
        for (int i = 1; i < N; ++i) {
            if (c1[i] == 0 && c2[i] == n - 1) return i;
        }
        return -1;
    }
};

Go

func findJudge(n int, trust [][]int) int {
	N := 1001
	c1 := make([]int, N)
	c2 := make([]int, N)
	for _, e := range trust {
		c1[e[0]]++
		c2[e[1]]++
	}
	for i := 1; i < N; i++ {
		if c1[i] == 0 && c2[i] == n-1 {
			return i
		}
	}
	return -1
}

...