【Day 29 】2022-01-09 - 997. 找到小镇的法官

[azl397985856]

997. 找到小镇的法官

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/find-the-town-judge/

前置知识

• 图

  题目描述

  
  在一个小镇里，按从 1 到 n 为 n 个人进行编号。传言称，这些人中有一个是小镇上的秘密法官。

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

小镇的法官不相信任何人。 每个人（除了小镇法官外）都信任小镇的法官。 只有一个人同时满足条件 1 和条件 2 。

给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示编号为 a 的人信任编号为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的编号。否则，返回 -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

示例 4：

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

示例 5：

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

 

提示：

1 <= n <= 1000 0 <= trust.length <= 104 trust[i].length == 2 trust[i] 互不相同 trust[i][0] != trust[i][1] 1 <= trust[i][0], trust[i][1] <= n

[yetfan]

思路 counter yyds

代码

import collections
class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        x = collections.Counter(x for x,y in trust)
        y = collections.Counter(y for x,y in trust)

        for i in range(1, n + 1):
            if x[i] == 0 and y[i] == n-1:
                return i

        return -1

复杂度 时间 O(n) 空间 O(n)

---

思路 新学的巧计 数组维护一个信任值，信任 -1，被信任+1。法官最后信任0，被信任n-1，所以一通操作后值为n-1。任何非法官人员都会因为信任他人导致值小于n-1，通过index直接查编号。这不比counter来的舒服。

代码

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        count = [0] * n
        for x, y in trust:
            count[x-1] -= 1
            count[y-1] += 1

        if n-1 in count:
            return count.index(n-1) + 1

        return -1

复杂度 时间 O(n) 空间 O(n)

[Bochengwan]

思路

通过一个set来找到出度为0的node，在判断它的indegree是否为N-1.

代码

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        trst_others = set(range(1,n+1))
        trust_times = defaultdict(int)

        for a_trust in trust:
            tr, tred = a_trust[0], a_trust[1]
            if tr in trst_others:
                trst_others.remove(tr)
            trust_times[tred]+=1
        if len(trst_others) != 1:
            return -1
        the_one = trst_others.pop()
        if trust_times[the_one]!=n-1:
            return -1
        return the_one

复杂度分析

• 时间复杂度：O(E)，其中 N 为数组长度。
• 空间复杂度：O(N)

[BpointA]

思路

找入度为n-1出度为0的点

代码

class Solution {
    public int findJudge(int n, int[][] trust) {
        HashMap<Integer,Integer> ins=new HashMap<>();
        HashMap<Integer,Integer> outs=new HashMap<>();
        for (int i=0;i<trust.length;i++)
        {
            outs.put(trust[i][0],outs.getOrDefault(trust[i][0],0)+1);
            ins.put(trust[i][1],ins.getOrDefault(trust[i][1],0)+1);

        }
        for (int j=1;j<n+1;j++)
        {
            if(ins.getOrDefault(j,0)==n-1 && outs.getOrDefault(j,0)==0)
            {
                return j;
            }
        }
        return -1;
    }
}

[zwmanman]

思路

Maintain two list of in/out degree. When in degree == n - 1 and out degree == 0 then is the judge

代码

（此处撰写代码）
class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        in_degree = [0] * (n + 1)
        out_degree = [0] * (n + 1)

        for pair in trust:
            in_degree[pair[1]] += 1
            out_degree[pair[0]] += 1

        for i in range(1, n + 1):
            if in_degree[i] == n - 1 and out_degree[i] == 0:
                return i

        return -1

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[zjsuper]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if n==1:
            return n
        dicin = defaultdict(list)
        dicout = defaultdict(list)

        for i in trust:
            dicin[i[1]].append(i[0])
            dicout[i[0]].append(i[1])
        for k,v in dicin.items():
            if len(v) == n-1:
                if not dicout[k]:
                    return k

        return -1

[CodeWithIris]

Question

Day29 997
https://leetcode-cn.com/problems/find-the-town-judge/

Note (Graph)

• Calculate each person's in and out degrees, and return the person with n-1 degrees.

Solution (C++)

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> count(n + 1);
        for(int i = 0; i < trust.size(); ++i){
            count[trust[i][0]] -= 1;
            count[trust[i][1]] += 1;
        }
        for(int i = 1; i <= n; ++i){
            if(count[i] == n - 1) return i;
        }
        return -1;
    }
};

Complexity

• T: O(trust.size() + n)
• S: O(n)

[Frederickfan]

    public int findJudge(int N, int[][] trust) {
        int[] count = new int[N+1];
        for (int[] t: trust) {
            count[t[0]]--;
            count[t[1]]++;
        }
        for (int i = 1; i <= N; ++i) {
            if (count[i] == N - 1) return i;
        }
        return -1;
    }

[CoreJa]

思路

• 朴素哈希：一开始没反应过来这题是图，变量命名用trusted和trusted_by_me太稀碎了
• 哈希：用哈希表标记节点的入度数和出度数，返回出度为0且入度为n-1的节点即可

代码

class Solution:
    # 朴素哈希：一开始没反应过来这题是图，变量命名用`trusted`和`trusted_by_me`太稀碎了
    def findJudge1(self, n: int, trust: List[List[int]]) -> int:
        if n == 1 and not len(trust):
            return 1
        trusted = defaultdict(set)
        trusted_by_me = defaultdict(bool)
        for t in trust:
            trusted[t[1]].add(t[0])
            trusted_by_me[t[0]] = True
        for person, x in trusted.items():
            if not trusted_by_me[person] and len(x) == n - 1:
                return person
        return -1

    # 哈希：用哈希表标记节点的入度数和出度数，返回出度为0且入度为n-1的节点即可
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        indegrees = Counter(y for _, y in trust)
        outdegrees = Counter(x for x, _ in trust)
        for i in range(1, n + 1):
            if outdegrees[i] == 0 and indegrees[i] == n - 1:
                return i
        return -1

[Liuxy94]

思路

第一次知道图，参考官方题解，将问题抽象为图，问题转为求图的入度和出度。用的是直接统计入度和出度的差，将两个数组降低为一个数组。

代码

class Solution:
     def findJudge(self, N, trust):
        count = [0] * (N + 1)
        for i, j in trust:
            count[i] -= 1
            count[j] += 1
        for i in range(1, N + 1):
            if count[i] == N - 1:
                return i
        return -1

复杂度分析

时间：O(n)

空间：O(n)

[zwx0641]

class Solution { public int findJudge(int n, int[][] trust) { int[][] arr = new int[n][2];

    for (int[] t : trust) {
        arr[t[0] - 1][0]++;
        arr[t[1] - 1][1]++;
    }

    for (int i = 0; i < n; i++) {
        if (arr[i][0] == 0 && arr[i][1] == n - 1) {
            return i + 1;
        }
    }
    return -1;
}

}

[xinhaoyi]

997. 找到小镇的法官

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

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

小镇法官不会信任任何人。 每个人（除了小镇法官）都信任这位小镇法官。 只有一个人同时满足属性 1 和属性 2 。 给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

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

思路一：两个map

代码

class Solution {
    public int findJudge(int n, int[][] trust) {
        Map<Integer, Integer> trustedMap = new HashMap<>();
        Map<Integer, Integer> trustMap = new HashMap<>();
        for(int i = 0; i < trust.length; i++){
            int trustOne = trust[i][0];
            int trustedOne = trust[i][1];
            trustedMap.put(trustedOne, trustedMap.getOrDefault(trustedOne, 0) + 1);
            trustMap.put(trustOne, 0);
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            if(!trustMap.containsKey(i) && ((trustedMap.containsKey(i) && trustedMap.get(i) == (n - 1)) || n == 1)){
                res.add(i);
            }
        }
        if(res.size() == 1){
            return res.get(0);
        }
        else{
            return -1;
        }
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

[MonkofEast]

997. Find the Town Judge

Click Me

Algo

1. Find (indeg) - (outDeg) == n - 1
2. Careful about array starting from 0

Code

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        # find a person with (indeg) - (outdeg) == 0
        count = [0] * (n + 1)
        for pair in trust:
            count[pair[0]] -= 1
            count[pair[1]] += 1
        for i in range(1, n + 1):
            if count[i] == n - 1: return i
        return -1

Comp

T: O(N)

S: O(N)

[ZhangNN2018]

class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        # a[i]表示第i个人的相信者的个数，入度数
        # b[i]表示第i个人相信的人的个数，出度数
        a = [0 for _ in range(n+1)]
        b = [0 for _ in range(n+1)]

        for x, y in trust:
            a[y] += 1
            b[x] += 1

        for i in range(1, n+1):
            if a[i] == n-1 and b[i] == 0:
                return i

        return -1    

时间复杂度：O(n) 空间复杂度：O(n)

[zhangzz2015]

思路

• 根据题意，为有向图，可记录入度除出度 inorder outorder ，找到 inorder = n-1 outorder = 0的人为法官，也可优化为一个inorder。时间复杂度为O(E+V)，空间复杂度为 O(V)

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {

        vector<int> inorder(n, 0); 

        for(int i=0; i< trust.size(); i++){            
            inorder[trust[i][0]-1]--;
            inorder[trust[i][1]-1]++;            
        }
        for(int i=0; i<n ; i++)
        {
            if(inorder[i]==n-1)
                return i+1; 
        }

        return -1; 

    }
};

[yingliucreates]

const findJudge = function(N, trust) {
    const truster = Array(N).fill(0); 
    const trustee = Array(N).fill(0); 

    for(let i = 0; i < trust.length; i++) {
        let [a, b] = trust[i];
        a--;
        b--;

        truster[a]++;
        trustee[b]++;
    }

    for(let i = 0; i < N; i++) {
        if (truster[i] == 0 && trustee[i] == N - 1) {
            return i + 1;
        }
    }

    return -1;
};

[laofuWF]

# iterate list and keep track a list of how many people trust person at given index + 1
# + 1 if someone is being trusted
# - 1 if someone is trusting another
# find the index of count that has total people - 1, which is the judge

# time: O(N)
# space: O(N)

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        count = [0 for i in range(n)]

        for t in trust:
            count[t[0] - 1] -= 1
            count[t[1] - 1] += 1

        for i, c in enumerate(count):
            if c == n - 1:
                return i + 1

        return -1

[cszys888]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        from collections import defaultdict
        if not trust and n == 1:
            return 1
        civil = defaultdict(int)
        judge = defaultdict(int)
        for element in trust:
            civil[element[0]] += 1
            judge[element[1]] += 1
        result = []
        for idx, count in judge.items():
            if count == n - 1 and civil[idx] == 0:
                return idx
        return -1

time complexity: O(N + M), N is the number of people, M is the length of trust array space complexity: O(N)

[ZacheryCao]

Idea

Graph. Check each node's degree of in and out. If one node's in degree is n-1 and its out degree is zero. That it's the judge/

Code:

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        In = {}
        Out = {}
        for i in range(1, n+1):
            In[i] = 0
            Out[i] = 0
        for p, t in trust:
            In[t] += 1
            Out[p] += 1
        for i in range(1, n+1):
            if i in In and In[i] == n-1 and Out[i] == 0:
                return i
        return -1

Complexity:

Time: O(max(n, edges)) Space: O(n)

[qihang-dai]

简单的图概念。

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] out = new int[n + 1], in = new int[n + 1];
        for(int[] cur : trust){
            out[cur[0]]++;
            in[cur[1]]++;
        }

        for(int i = 1; i< n+1; i++){
            if(out[i] == 0 && in[i] == n - 1) return i;
        }

        return -1;
    }
}

[yan0327]

思路： 用一个哈希表【数组】记录入度，出度次数。 然后找出入度为n-1，出度为0的i 若没有，则返回-1

func findJudge(n int, trust [][]int) int {
    in := make([]int,n+1)
    out := make([]int,n+1)
    for _,x := range trust{
        in[x[1]]++
        out[x[0]]++
    }
    for i:=1;i<=n;i++{
        if in[i]==n-1&&out[i] == 0{
            return i
        }
    }
    return -1
}

时间复杂度O（N） 空间复杂度O（N）

[RocJeMaintiendrai]

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] count = new int[n + 1];
        for(int[] t : trust) {
            count[t[0]]--;
            count[t[1]]++;
        }
        for(int i = 1; i <= n; i++) {
            if(count[i] == n - 1) return i;
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[Tesla-1i]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        from collections import defaultdict
        if not trust and n == 1:
            return 1
        civil = defaultdict(int)
        judge = defaultdict(int)
        for element in trust:
            civil[element[0]] += 1
            judge[element[1]] += 1
        result = []
        for idx, count in judge.items():
            if count == n - 1 and civil[idx] == 0:
                return idx
        return -1

[didiyang4759]

思路； 遍历trust，因此法官这个节点的入度是 n-1, 出度是 0。

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        inDegrees = Counter(y for _, y in trust)
        outDegrees = Counter(x for x, _ in trust)
        return next((i for i in range(1, n + 1) if inDegrees[i] == n - 1 and outDegrees[i] == 0), -1)

时间复杂度 O(n+m) 空间复杂度O(n)

[zhiyuanpeng]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        in_degree, out_degree = [0]*(n+1), [0]*(n+1)
        for f, t in trust:
            in_degree[t] += 1
            out_degree[f] += 1
        for i in range(1, n+1):
            if in_degree[i] == n-1 and out_degree[i] == 0:
                return i
        return -1

time O(N), space O(N)

[LinnSky]

思路

找到一个人没有左边的关系，右边的关系等于n-1 怎么表现这种关系， 创建两个长度为n+1的数组分别表示左边的关系和右边的关系，记录每次左右两边的关系数量

代码

    var findJudge = function(n, trust) {
        const inDegree = new Array(n + 1), outDegree = new Array(n + 1)
    cnts.fill(0)
    out.fill(0)
    for(const t of trust){
        inDegree[t[1]]++
        outDegree[t[0]]++
    }
    for(let i = 1; i <= n; i++)
        if(outDegree[i] == 0 && inDegree[i] == n - 1)
            return i
    return -1
 };

复杂度分析

• 时间复杂度O(N)
• 空间复杂度O(N)

[xuhzyy]

思路

通过入度和出度来表示被信任和信任的人数，入度=n-1和出度=0即为法官

代码

class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        indegree = [0] * (n + 1)
        outdegree = [0] * (n + 1)
        for a, b in trust:
            outdegree[a] += 1
            indegree[b] += 1
        for i in range(1, n+1):
            if outdegree[i] == 0 and indegree[i] == n - 1:
                return i
        return -1

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

[ZJP1483469269]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        cnt = [0] * n
        for ts in trust:
            cnt[ts[0]-1] -= 1
            cnt[ts[1]-1] += 1

        for i in range(n):
            if cnt[i] == n-1:
                return i+1
        return -1

[GaoMinghao]

代码

class Solution {
    public int findJudge(int n, int[][] trust) {
        if(trust.length==0) {
            if(n==1)
                return 1;
            else
                return -1;
        }
        int result = -1;
        Set<Integer> trusted = new HashSet<>();
        Map<Integer, Integer> records = new HashMap<>();
        for(int[] trustPair:trust) {
            records.put(trustPair[1], records.getOrDefault(trustPair[1],0)+1);
            trusted.add(trustPair[0]);
        }
        for(Map.Entry<Integer, Integer> singleRecord : records.entrySet()) {
            if(singleRecord.getValue() == n-1) {
                if(!trusted.contains(singleRecord.getKey())) {
                    result = singleRecord.getKey();
                }
            }
        }
        return result;
    }
}

复杂度

时间复杂度O(N) 空间复杂度O(N)

[ninghuang456]

public int findJudge(int n, int[][] trust) {
        if (trust.length < n - 1) {
            return -1;
        }
        int[] arr = new int[n+1];
        for(int[] tr : trust){
            arr[tr[0]]--;
            arr[tr[1]]++;
        }
        for(int p=1;p<arr.length;p++){
            if(arr[p] == n-1)
                return p;
        }
        return -1;
    }
// Time O(n),   Space O(n)

[wenjialu]


# thought 图： 入度记录：被相信的人（号码 trust【i】【1】）：被多少人相信（人数） 出度记录：相信别人的人（号码 trust【i】【0】）：相信多少人（人数） 法官：被除了自己的所有人数所相信（入度=n-1），不相信任何人（出度=0）。

code

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:

        in_degree = Counter(y for _,y in trust)
        out_degree = Counter(x for x,_ in trust)
        # print(out_degree, in_degree)   
        for i in range(1, n + 1): # n represent n people
            if in_degree[i] == n - 1 and out_degree[i] == 0:
                return i 
        return -1        

com

Time: O(m + n), m 是trust的长度？？？？？？ Space:O(n)

[nonevsnull]

思路

//s6

• 思路与解法

• 直接转化为degree计算；

代码

//s6
class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] netDegree = new int[n];

        for(int i = 0;i < trust.length;i++){
            int[] degree = trust[i];
            netDegree[degree[0]-1]--;
            netDegree[degree[1]-1]++;
        }
        for(int i = 0;i < n;i++){
            if(netDegree[i] == n-1){
                return i+1;
            }
        }
        return -1;
    }
}

复杂度

根据题目的两个变量，即edges和vertices time: O(trust.length) space: O(n)

[Flower-F]

解题思路

我们可以将小镇中的人们之间的信任关系抽象为图的边，这样问题就转化为求图中入度为 n - 1 并且出度为 0 的点。进一步简化，根据前面的分析，显然可知若存在法官，则 n - 1 为出度与入度差的最大值，因此可以直接求解是否存在出度和入度差为 n - 1 的图即可。

代码

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function(n, trust) {
    if (trust.length === 0 && n === 1) {
        return 1;
    }
    const counter = new Map();
    for (const path of trust) {
        counter.set(path[0], (counter.get(path[0]) || 0) - 1); // 入度
        counter.set(path[1], (counter.get(path[1]) || 0) + 1); // 出度
    }
    for (const elem of counter) {
        if (elem[1] === n - 1) {
            return elem[0];
        }
    }
    return -1;
};

复杂度

时间：O(N) 空间：O(N)

[yijing-wu]

思路

遍历所有节点并统计入度和出度，法官节点的入度是n-1，出度为0. 找到符合条件的节点返回，不存在符合条件的点，返回-1

代码

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] inDegrees = new int[n + 1];
        int[] outDegrees = new int[n + 1];
        for (int[] edge : trust) {
            int x = edge[0], y = edge[1];
            ++inDegrees[y];
            ++outDegrees[x];
        }
        for (int i = 1; i <= n; ++i) {
            if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}

复杂度分析

• Time Complexitty = O(n+m), 其中n为节点的数量，m为trust的长度
• Space Complexitty = O(n)

[MengyuZang]

Solution

1. Graph. (inDeg/be trusted) - (outDeg/trust) == n - 1.
2. Store each person's degree in an array. The judge trusts 0 time and be trusted n-1 times，so their degree is n-1. Other people's should be less than n-1 as they trust others.

Other methods

1. Can use 2 arrays, one for inDeg, and another for outDeg. Judge should be n-1 and 0. But one array works as well in this problem.

Code

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] count = new int[n];
        for(int[] pair: trust){
            count[pair[0] - 1]--;
            count[pair[1] - 1]++;
        }
        for(int i = 0; i < count.length; i++){
            if(count[i] == n-1) return i + 1;
        }
        return -1;
    }
}

Complexity

T: O(max(n, trust.length))

S: O(n)

[wangzehan123]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int findJudge(int n, int[][] trust) {
        boolean[] belive = new boolean[n+1];
        int[] ticket = new int[n+1];
        for(int[] t:trust){
            belive[t[0]] = true;
            ++ticket[t[1]];
        }

        for(int i = 1; i <= n; i++)
            if(!belive[i] && ticket[i]==n-1)
                return i;

        return -1;
    }
}

[haixiaolu]

思路

抄的答案

代码 / Python

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        inDegrees = [0] * (n + 1)
        outDegrees = [0] * (n + 1)

        for x, y in trust:
            inDegrees[y]  += 1
            outDegrees[x] += 1

        for i in range(1, n + 1):
            if inDegrees[i] == n - 1 and outDegrees[i] == 0:
                return i
        return -1

复杂度分析

• 时间复杂度： O(n)
• 空间复杂度: O(n)

[tongxw]

思路

统计入度为n-1且出度为0的顶点

    public int findJudge(int n, int[][] trust) {
        int[] counts = new int[n + 1];
        for (int[] t : trust) {
            // trust[0] -> trust[1]
            counts[t[1]]++;
            counts[t[0]]--;
        }

        for (int i=1; i<=n; i++) {
            if (counts[i] == n - 1) {
                return i;
            }
        }

        return -1;
    }

TC: O(V +E) SC: O(V)

[feifan-bai]

思路

1. 将小镇中的人们之间的信任关系抽象为图的边，图中的点是小镇中的人
2. 问题就转化为求图中入度（或出度）为 n - 1 并且出度（或入度）为 0的点

代码

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

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[HondryTravis]

思路

抽象为图，出度和入度

代码

var findJudge = function (n, trust) {
  // toBelieve 相信别人
  // beBelieved 被别人相信
  const toBelieve = Array(n).fill(0), beBelieved = Array(n).fill(0)
  for (const [a, b] of trust) {
    toBelieve[a - 1]++
    beBelieved[b - 1]++
  }

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

复杂度

时间复杂度 O(n)

空间复杂度 O(n)

[zol013]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        indegree = [0] * n
        outdegree = [0] * n
        for relation in trust:
            indegree[relation[1] - 1] += 1
            outdegree[relation[0] - 1] += 1

        for i in range(n):
            if indegree[i] == n - 1 and outdegree[i] == 0:
                return i + 1

        return -1

TC: O(N) SC: O(N)

[a244629128]

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function(n, trust) {
    var judgeMap = {};
    var peoplesMap = {};

    for(let i = 1;i<=n;i++){
        judgeMap[i] = 0;
        peoplesMap[i] = 0;
    }
     for(let j = 0;j<trust.length;j++){
        judgeMap[trust[j][1]] ++;
        peoplesMap[trust[j][0]] ++;
    }
    var mapKey = Object.keys(peoplesMap)
    var judgeID;
    var twoJudges = false;
    for(let k = 0; k<mapKey.length;k++){
        var currID = mapKey[k];
        if(peoplesMap[currID] === 0 && judgeMap[currID] === n-1){
            if(judgeID){
                twoJudges = true;
            }
             judgeID = currID;
        }
    }
    console.log(judgeMap)
   if(!twoJudges && judgeID){
       return judgeID;
   }else{
       return -1;
   }
};

[Toms-BigData]

【Day 29】997. 找到小镇的法官

思路

新建一个list，遍历trust,将出现在trust[i][0]的值-1，出现在trust[i][1]的值加1，最后再遍历一遍list，值为n-1的就是ans

golang 代码

func findJudge(n int, trust [][]int) int { if n==1 && len(trust) == 0{ return 1 } anslist:=make([]int,n+1) for i := 0; i < len(trust); i++ { anslist[trust[i][0]] -=1 anslist[trust[i][1]] += 1 } for i := 0; i < len(anslist); i++ { if anslist[i] == n-1{ return i } } return -1 }

复杂度

时间:O(n) 空间:O(n)

[YuyingLiu2021]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        #solution 1
        l1 = []
        l2 = []
        for i in range(len(trust)):
            l1.append(trust[i][0])
            l2.append(trust[i][1])
        for i in range(1, n+1):
            if i not in l1 and l2.count(i) == n-1:
                return i
        return -1

[LannyX]

思路

求图的入度和出度

代码

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] in = new int[n+1], out = new int[n+1];
        for(int[] edge : trust){
            int a = edge[0], b = edge[1];
            in[b]++;
            out[a]++;
        }
        for(int i = 1; i <= n; i++){
            if(in[i] == n - 1 && out[i] == 0 ){
                return i;
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[simbafl]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        l1 = []
        l2 = []
        for i in range(len(trust)):
            l1.append(trust[i][0])
            l2.append(trust[i][1])
        for i in range(1, n+1):
            if i not in l1 and l2.count(i) == n-1:
                return i
        return -1

[Yachen-Guo]

思路

这是一道图的基础题，关键在于是否是法官的判定，即所有人都信任TA，TA不信任任何人。转化成图的角度即是该点的出度为n-1，入度为0. 因此采用simulation的方法模拟这个过程，建立in list和out list，并通过遍历筛选符合条件的i。

代码

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] in = new int[n+1];
        int[] out = new int[n+1];
        for(int[] person: trust){
            int num = person[0];
            int tru = person[1];
            out[num]++;
            in[tru]++;
        }
        for(int i = 1; i <= n; i++){
            if(in[i]==n-1 && out[i] == 0) return i;
        }
        return -1;
    }
}

[jiaqiliu37]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        indeg = [0]*n
        outdeg = [0]*n
        for a, b in trust:
            outdeg[a - 1] += 1
            indeg[b - 1] += 1

        ans = -1
        for i in range(n):
            if outdeg[i] == 0 and indeg[i] == n - 1:
                ans = i + 1

        return ans
``` Time complexity O(n)
Sapce complexity O(n)

[zol013]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        indegree = [0] * n
        outdegree = [0] * n
        for relation in trust:
            indegree[relation[1] - 1] += 1
            outdegree[relation[0] - 1] += 1

        for i in range(n):
            if indegree[i] == n - 1 and outdegree[i] == 0:
                return i + 1

        return -1

[Zhang6260]

JAVA版本

使用二个数组来进行存储。

class Solution {
    public int findJudge(int n, int[][] trust) {
        //用二个数组来记录 相信他的人，和被他信息的人
        int  trust_1[] = new int[n];//相信的人
        int  trust_ed[] = new int[n];//被相信的人
        for(int i=0;i<trust.length;i++){
            trust_1[trust[i][0]-1]=1;
            trust_ed[trust[i][1]-1]+=1;
        }
        for(int i=0;i< n;i++){
            if(trust_1[i]==0&&trust_ed[i]==n-1){
                return i+1;//从1开始的  固要加1
            }
        }
        return -1;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

[uniqlell]

思路：图的模拟

分析:

• 不相信任何人说明出度为0.
• 每个人都相信说明入度为n-1

class Solution {
    public int findJudge(int n, int[][] trust) {
        int []out = new int[n+1];
        int []in = new int[n+1];
        for(int[]relation :trust){
            //统计出度
            out[relation[0]]++;
            //统计入度
            in[relation[1]]++;
        }
        for(int i=1;i<in.length;i++){
            if(in[i]==n-1&&out[i]==0)return i;
        }
        return -1;
    }
}