【Day 29 】2022-04-29 - 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

[zjsuper]

class Solution: def findJudge(self, n: int, trust: List[List[int]]) -> int: indegree,outdegree = [0](n+1),[0](n+1) for i,j in trust: indegree[j] +=1 outdegree[i] +=1 for i in range(1,n+1): if indegree[i] == n-1: if outdegree[i] == 0: return i return -1

[rzhao010]

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

[Yongxi-Zhou]

思路

建图，返回出度为0和入度为n-1的点。

代码

    class Solution(object):
        def findJudge(self, n, trust):
            """
            :type n: int
            :type trust: List[List[int]]
            :rtype: int
            """
            if not trust and n == 1:
                return 1
            graph = collections.defaultdict(list)
            outdegree = collections.defaultdict(int)
            indegree = collections.defaultdict(int)
            for item in trust:
                graph[item[0]].append(item[1])
                indegree[item[1]] += 1
                outdegree[item[0]] += 1
                if item[1] not in outdegree:
                    outdegree[item[1]] = 0

            for key in outdegree.keys():
                if outdegree[key] == 0 and indegree[key] == n - 1:
                    return key
            return -1

复杂度

time O(N) space O(N)

[MichaelXi3]

Idea

• Graph

• Judge <-- In-degree - out-degree = n-1

  Code

  class Solution {
  public int findJudge(int n, int[][] trust) {
      // Array that counts the "in-degree - out-degree" of each point
      int[] count = new int[n+1];
  
      // Iterate through the trust relationship and count the degree differences
      for (int[] i : trust) {
          count[i[0]]--;
          count[i[1]]++;
      }
  
      // Return the index of judge, if have
      for (int i=1; i<=n; i++) {
          if (count[i] == n-1) {
              return i;
          }
      }
      return -1;
  }
  }

  Complexity

• Time Complexity: O(N)
• Space Complexity: O(N)

[ZacheryCao]

Idea

Graph. Check the indegrees and outdegrees.

Code

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if n == 1 and not trust:
            return 1
        inDegree = collections.defaultdict(set)
        outDegree = collections.defaultdict(set)
        maxOut = [0, 1]
        for i in trust:
            s, e = i
            inDegree[e].add(s)
            outDegree[s].add(e)
            if len(inDegree[e])>maxOut[0]:
                maxOut = [len(inDegree[e]), e]
        if len(outDegree) != n-1 or len(inDegree[maxOut[1]]) != n-1:
            return -1
        return maxOut[1]

Complexity:

Time: O(edge) Space: O(nodes * nodes)

[forestie9]

Ideas

Graph, indegree and outdegree

def findJudge(self, N: int, trust: List[List[int]]) -> int:

    if len(trust) < N - 1:
        return -1

    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 indegree[i] == N - 1 and outdegree[i] == 0:
            return i
    return -1

O(E) time, O(N) space

[james20141606]

Day 29: 997. Find the Town Judge (array, hashtable, graph)

• Problem Link

  • 997. Find the Town Judge

• Ideas

  • Count the in, and use set to judge if the vertex is seen in out_vertex. if count = N-1 and is not seen in out_vertex it is the judge. But we need to take care of several edge cases.
  • Use graph. We could use a graph, and count for each vertex, we have the edge as list. We count the in and out degrees for each vertex. And the judge satisfies the in_degree == N-1 and out_degree == 0.
  • Optimize a little bit. We know that in this case, the difference between in and out should be exactly N-1. Since the max in is N-1 and the min out is 0. So if the difference is N-1, it must be the judge.

• Complexity: hash table and bucket

  • Time: O(N)
  • Space: O(N)

• Code

#need a n-1 trust and not trust for others. 
class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if len(trust) == n:
            return -1
        if len(trust) == 0: #only judge itself
            return 1 if n == 1 else -1
        count = Counter([i[1] for i in trust])
        out_vertex = set([i[0] for i in trust])
        res = list(map(lambda x: x[0], filter(lambda x: x[1] ==n-1, count.items())))
        res = [i for i in res if i not in out_vertex]
        return res[0] if len(res) >0 else -1

#some similar idea: https://leetcode-cn.com/problems/find-the-town-judge/solution/997zhao-dao-xiao-zhen-de-fa-guan-ha-xi-b-x7eu/
class Solution:
    def findJudge(self, n, trust):
        people, judge = set(range(1, n + 1)), defaultdict(int)
        for p, j in trust:
            if p in people:
                people.remove(p)
            judge[j] += 1
        if len(people) != 1:
            return -1
        person = people.pop()
        return -1 if judge.get(person, 0) != n - 1 else person

#we could use graph, and count for each vertex, we have the edge as list. We count the in and out degrees for each vertex. And the judge satisfies the in degree == N-1 and out degree == 0

class Solution:
     def findJudge(self, N, trust):
        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

#to optimize, we know that in this case, the difference between in and out should be exactly N-1. Since the max in is N-1 and the min out is 0. So if the difference is N-1, it must be the judge.
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

• other resources:
  • https://leetcode-cn.com/problems/find-the-town-judge/solution/997zhao-dao-xiao-zhen-de-fa-guan-ha-xi-b-x7eu/

[1973719588]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if len(trust) == 0:
            if n == 1:
                return 1
            else:
                return -1

        ren = []
        mayfa = {}

        for a, b in trust:
            ren.append(a)
            if b not in mayfa:
                mayfa[b] = 1
            else:
                mayfa[b] += 1

        ren = set(ren)
        if n > len(ren) + 1:
            return -1
        ls= []

        for x in mayfa:
            if mayfa[x] == len(ren):
                ls.append(x)

        if len(ls) == 0:
            return -1
        for c in ls:
            if c not in ren:
                return c

        return -1

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

[huiminren]

"""python 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) """

[houmk1212]

思路

在图中寻找入度为n-1，出度为0的顶点

代码

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[][] graph = new int[n + 1][n + 1];
        for (int[] edge : trust) {
            int a = edge[0];
            int b = edge[1];
            graph[a][b] = 1;
        }

        for (int i = 1; i <= n; i++) {
            if (inDot(graph, i, n) == n - 1 && outDot(graph, i, n) == 0) {
                return i;
            }
        }
        return -1;
    }

    private int inDot(int[][] graph, int k, int n) {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (graph[i][k] == 1) {
                res++;
            }
        }
        return res;
    }

    private int outDot(int[][] graph, int k, int n) {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (graph[k][i] == 1) {
                res++;
            }
        }
        return res;
    }
}

复杂度

• 时间复杂度：O（N2）
• 空间复杂度：O（N2）

[zhulin1110]

题目地址(997. 找到小镇的法官)

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

题目描述

小镇里有 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 <= 104
trust[i].length == 2
trust 中的所有trust[i] = [ai, bi] 互不相同
ai != bi
1 <= ai, bi <= n

前置知识

• 有向图

思路

每个人是图的节点，trust 的元素 trust[i] 是图的有向边，从 trust[i][0] 指向 trust[i][1]。我们可以遍历 trust，统计每个节点的入度和出度，存储在inDegrees 和 outDegrees 中。

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function(n, trust) {
  const inDegrees = new Array(n + 1).fill(0);
  const outDegrees = new Array(n + 1).fill(0);
  for (const edge of trust) {
      const x = edge[0], y = edge[1];
      ++inDegrees[y];
      ++outDegrees[x];
  }
  for (let i = 1; i <= n; ++i) {
      if (inDegrees[i] === n - 1 && outDegrees[i] === 0) {
        return i;
      }
  }
  return -1;
};

复杂度分析

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

[ShawYuan97]

思路

• 计算图的入度和出度

关键点

• 如何存储每个节点的入度和出度

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        """
        寻找法官 也就是在图中需按照入度为n-1,出度为0的节点是否存在
        """
        in_degree = [0] * (n+1)
        out_degree = [0] * (n+1)

        for a,b in trust:
            out_degree[a] += 1
            in_degree[b] += 1
        for in_,out_ in zip(in_degree,out_degree):
            if in_ == n-1 and out_ == 0:
                return in_degree[1:].index(in_)+1
        return -1

复杂度分析

令 n 为数组长度。

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

[KelvinG-LGTM]

思路

学习下官方代码 next函数的用法: 第二个参数是默认返回值. 既如果没有法官就返回-1

代码

# 自己代码
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)
        res = -1
        for i in range(1, n + 1): 
            if inDegrees[i] == n - 1 and outDegrees[i] == 0: 
                res = i

        return res 

# 官方代码
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(len(trust))

空间复杂度

O(len(trust))

反思

1. 是find celebrity的前置问题.

[Magua-hub]

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
    vector<int> din(n + 1),  dout(n + 1);
    for(auto p : trust) {
        int a = p[0], b = p[1];
        din[b] ++;
        dout[a] ++;
    }

    int res = -1;
    for(int i = 1; i <= n; i ++) {
        if(!dout[i] && din[i] == n - 1) {
            if(res != -1) res = -1;
            res = i;
        }
    }
    return res;
    }
};

[caterpillar-0]

思路

模拟图，出入度，使用一个数组，当存在==n-1就是法官

代码

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

复杂度分析

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

[xixiao51]

Idea

For this graph, the outdegree of a person represents the number of other people trust. The indegree of a person represents the number of people trusted by that person.

Code

class Solution {
    public int findJudge(int n, int[][] trust) {
        if(trust.length < n - 1) {
            return -1;
        }
        int[] indegrees = new int[n + 1];
        int[] outdegrees = new int[n + 1];

        for(int[] relation: trust) {
            outdegrees[relation[0]]++;
            indegrees[relation[1]]++;
        }

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

        return -1;
    }
}

Complexity Analysis

• Time complexity: O(E), E is the number of edges;
• Space complexity: O(N), N is the number of people.

[577961141]

997. 找到小镇的法官

题目链接

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

题目思路

• 图

可以把这道题想象成图的出度和入度来做

先看题目的描述：

1. 小镇的法官不会相信任何人，代表着法官的出度为0
2. 每个人（除了小镇法官）都信任这位小镇法官，代表着这位小镇法官的入度为n-1
3. 只有一个人同时满足属性 1 和属性 2 。那么代表法官是唯一的，题解如下

题目的题解code

class Solution {

    /**
     * @param Integer $n
     * @param Integer[][] $trust
     * @return Integer
     */
    function findJudge($n, $trust) {
        $inDegress = [];
        $outDegress = [];

        foreach ($trust as $val) {
            $inDegress[$val[1]]++;
            $outDegress[$val[0]]++;
        }

//        var_dump($inDegress, $outDegress );die;

        for ($i = 1; $i <= $n; $i++) {
            if ($inDegress[$i] == $n - 1 && $outDegress[$i] == 0) {
                return $i;
            }
        }

        return -1;
    }
}

func findJudge(n int, trust [][]int) int {
    inDegress := make([]int, n+1)
    outDegerss := make([]int, n+1)

    for _, val := range trust {
        inDegress[val[1]]++
        outDegerss[val[0]]++
    }

    for i := 1; i <= n; i++ {
        if inDegress[i] == n-1 && outDegerss[i] == 0 {
            return i
        }
    }

    return -1
}

时间和空间复杂度

• 时间复杂度：O(n+m),m代表的是trust数组的个数(遍寻多少次)，n代表的是小镇的人的个数（也要遍寻）
• 空间复杂度：O(n),记录各个节点的入度和出度需要O(n)的空间

[hyh331]

Day29 思路

根据题意找到出度为0且入度为n-1的那个人编号即可。

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        //定义长度为n+1的in和out，存放信任度
        vector<int> in(n+1), out(n+1);
        //遍历trust二维数组，第一个位置是代表信任别人，第二个位置代表被别人信任
        for (auto &x : trust) {
            in[x[1]]++; out[x[0]]++;
        }
       //若是法官，则入度为n-1，出度为0
        for (int i = 1; i <= n; i++) {
            if (in[i] == n-1 && out[i] == 0)
                return i;
        }
        return -1;
    }
};

复杂度分析

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

[zqwwei]

Code

    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if not trust and n == 1: return 1
        truster = []
        trusted_count = defaultdict(int)
        for p1, p2 in trust:
            truster.append(p1)
            trusted_count[p2] += 1
        for trustee, count in trusted_count.items():
            if count == n-1 and trustee not in truster:
                return trustee
        else:
            return -1

timeO(n)
spaceO(n)

[gitbingsun]

题目地址(997. 找到小镇的法官)

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

题目描述

小镇里有 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 <= 104
trust[i].length == 2
trust 中的所有trust[i] = [ai, bi] 互不相同
ai != bi
1 <= ai, bi <= n

思路

用一个vector size of n 存目前的人有被多少人trust, or set to be -1 if this person trust someone else

代码

class Solution { public: int findJudge(int n, vector<vector>& trust) { // edge case if (n == 1 && trust.size() == 0) return 1;

    vector<int> num(n+1,0);
    for (auto v : trust) {
        // v[0] trust v[1] so v[0] cannot be the judge
        num.at(v[0]) = -1; 
        num.at(v[1]) += 1;
    }

    for (int i = 0; i < num.size(); i++) {
        if (num.at(i) == n-1) 
            return i;
    }
    return -1;

}

};

**复杂度分析**

令 n 为数组长度。

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

[freedom0123]

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;
    }
}

[currybeefer]

int findJudge(int n, vector<vector<int>>& trust) 
    {
        if (trust.empty() && n == 1) 
            return 1;
        unordered_map<int, int> count;
        for (vector<int>& relation : trust)
        {
            count[relation[0]] += -1;
            count[relation[1]] += 1;
        }
        int no_k = -1;
        for (auto kvp : count)
        {
            if (kvp.second == (n-1)) 
                no_k = kvp.first;
        }
        return no_k;
    }

[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

[Ellie-Wu05]

思路：Graph

学习graph的第一天，没写过任何题目所以看题解写的 学习了indegree 和 outdegree

代码

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

复杂度分析：

时间：On 空间：On

[TimmmYang]

思路

将人作为图的节点统计出入度。如果一个节点的出度为0入度为n-1则返回结果。

代码

from collections import Counter
class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        l1 = Counter(x for x,y in trust)
        l2 = Counter(y for x,y in trust)
        for i in range(1, n+1):
            if l1[i] == 0 and l2[i] == n-1:
                return i
        return -1

复杂度

时间复杂度：O(n+m)，m为trust长度

空间复杂度：O(n)

[Geek-LX]

4.29

思路：

可以遍历每个节点的入度和出度，如果找到一个符合条件的节点，由于题目保证只有一个法官，我们可以直接返回结果；如果不存在符合条件的点，则返回 -1−1。

代码：

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)

[m908]

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> inDegree(n + 1), outDegree(n + 1);
        for (auto &_trust: trust) {
            ++inDegree[_trust[1]];
            ++outDegree[_trust[0]];
        }
        for (int i = 1; i <= n; ++i)
            if (inDegree[i] == n - 1 && !outDegree[i])    return i;
        return -1;
    }
};

[revisegoal]

有向图

转换为有向图，找出度为0，入度为n - 1的点

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

• time: O(m + n)
• space: O(n)

[MoonLee001]

思路

统计有向图的入度和出度

代码

var findJudge = function(n, trust) {
    const inDegrees = new Array(n + 1).fill(0);
    const outDegrees = new Array(n + 1).fill(0);

    for (let i = 0; i < trust.length; i++) {
        const [x, y] = trust[i];
        ++inDegrees[y];
        ++outDegrees[x];
    }

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

    return -1;
};

复杂地分析

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

[YuyingLiu2021]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        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

[mo660]

思路

入度为n-1出度为0的点是法官

代码

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        if (trust.empty() && n == 1) return 1;
        unordered_map<int,int>mp;
        for (auto it : trust){
            mp[it[0]]--;
            mp[it[1]]++;
        }
        for (auto it : mp){
            if (it.second == n-1)
                return it.first;
        }
        return -1;
    }
};

[biscuit279]

思路

寻找入度为n-1同时出度为0的节点

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        in_degree,out_degree = [0] * (n+1), [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)

[L-SUI]

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function(n, trust) {
    const inDegrees = new Array(n + 1).fill(0);
    const outDegrees = new Array(n + 1).fill(0);
    for (const edge of trust) {
        const x = edge[0], y = edge[1];
        ++inDegrees[y];
        ++outDegrees[x];
    }
    for (let i = 1; i <= n; ++i) {
        if (inDegrees[i] === n - 1 && outDegrees[i] === 0) {
            return i;
        }
    }
    return -1;
};

[JasonHe-WQ]

代码：

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

[xiayuhui231]

题目

找到小镇的法官

代码

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> inDegree(n + 1 , 0);
        vector<int> outDegree(n + 1 , 0);

        for(const auto pairs : trust){
            inDegree[pairs[1]] += 1;
            outDegree[pairs[0]] += 1;
        }

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

复杂度

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

[kite-fly6618]

思路：

求图中，入度为n-1,出度为0的值

代码：

 // 求图中，入度为n-1,出度为0的值
var findJudge = function(n, trust) {
    let indegree = new Array(n+1).fill(0)
    let outdegree = new Array(n+1).fill(0)
    for (let i = 0;i<trust.length;i++) {
        let x = trust[i][0] // x出度+1
        let y = trust[i][1] // y入度+1        
        outdegree[x]++
        indegree[y]++
    }
    // 查找符合条件
    for (let i = 1;i <= n;i++) {
        if (indegree[i]===n-1&&outdegree[i]===0) {
            return i
        }
    }
    return -1
};

复杂度：

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

[JiangWenqi]

想错了，一开始还打算用unionfind做 结果就是计算出度入度就行

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

O(n) O(n)

[oneline-wsq]

代码

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

        for i in range(len(who_t)):
            if who_t[i]==0 and trusted[i]==n-1:
                return i+1
        return -1

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[physicshi]

思路

图，n 个节点，求其他节点都入度，但是该节点不出度

代码

impl Solution {
    pub fn find_judge(n: i32, trust: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut trusted = vec![0; n + 1];
        let mut trusts = vec![0; n + 1];

        for pair in trust {
            let (a, b) = (pair[0] as usize, pair[1] as usize);
            trusts[a] += 1;
            trusted[b] += 1;
        }

        for i in 1..n + 1 {
            if trusts[i] == 0 && trusted[i] == n - 1 {
                return i as i32;
            }
        }

        -1
    }
}

复杂度

• 时间复杂度：O(n+m)，其中 mm 是 trust 的长度。首先需要遍历 trust 计算出 inDegrees 和 outDegrees，然后需要遍历 inDegrees 和 outDegrees 来确定法官
• 空间复杂度：O(n)

[zhishinaigai]

思路

计算入度和出度

代码

int findJudge(int n, vector<vector<int>>& trust) {
        vector <int> in(n+1);
        vector <int> out(n+1);
        for(auto& edge:trust){
            int x=edge[0];
            int y=edge[1];
            ++in[y];
            ++out[x];
        }
        for(int i=1;i<=n;i++){
            if(in[i]==n-1&&out[i]==0) return i;
        }
        return -1;
    }

[flaming-cl]

997. Find the Town Judge

Solution

• The key to solve this problem is to focus on the two conditions:
  • The town judge trusts nobody.
  • Everybody (except for the town judge) trusts the town judge.
• We will build two arrays to record how people trust others and how they are trusted by others. If someone is the judge:
  • that person will have n - 1 people that trust him/her.
  • that person will trust 0 others.

Complexity

• Time：O(N)

• Space: O(N)

  Code

  /**
  * @param {number} n
  * @param {number[][]} trust
  * @return {number}
  */
  var findJudge = function(n, trust) {
  const trustedByOthersCount = new Array(n + 1).fill(0);
  const trustOthersCount = new Array(n + 1).fill(0);
  for (const trustInfo of trust) {
    ++trustOthersCount[trustInfo[0]];
    ++trustedByOthersCount[trustInfo[1]];
  }
  
  for (let i = 1; i <= n; i++) {
    if (trustedByOthersCount[i] === n - 1 && trustOthersCount[i] === 0) {
      return i;
    }
  }
  return -1;
  };

[TonyLee017]

思路

• 求图中各结点的出度、入度。满足出度为0，入度为n-1的结点即为所求。

  代码

  class Solution:
  def findJudge(self, n: int, trust: List[List[int]]) -> int:
      if n == 1: return 1
      # 统计出度、入度
      # out_degree = {}
      # in_degree = {}
      # for i in range(n):
      #     out_degree[i+1] = 0
      #     in_degree[i+1] = 0
      # for i in range(len(trust)):
      #     if trust[i][0] in out_degree:
      #         out_degree[trust[i][0]] += 1
      #     if trust[i][1] in in_degree:
      #         in_degree[trust[i][1]] += 1
  
      out_degree = Counter(x for x, _ in trust)
      in_degree = Counter(y for _,y in trust)
      for i in range(1,n+1):
          if out_degree[i] == 0 and in_degree[i] == n-1:
              return i
      return -1

  复杂度分析：

• 时间复杂度：O(n+m)，其中n为结点数，m为trust数组长度
• 空间复杂度：O(n)

[zzz607]

思路

对于trust数组中的任意一个值[ai, bi]，记录ai不是法官，同时记录 bi被信任的票数。遍历完trust数组之后，查看是否有人没有信任过任 何人并且被n-1个人信任

代码

func findJudge(n int, trust [][]int) int {
    var candidate = make([]bool, n+1)
    var vote = make([]int, n+1)

    for _, item := range trust {
        candidate[item[0]] = true
        vote[item[1]]++
    }

    for i := 1; i <= n; i++ {
        if !candidate[i] && vote[i] == n - 1 {return i}
    }

    return -1
}

复杂度分析

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

[wychmod]

思路

创建一个哈希表，创建一个数组，哈希表记录每个人有没有被相信过，数组记录，那个人最被相信。之后找出被n-1相信过的人和这个人有没有相信过其他人。

代码

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if n == 1:
            return 1
        dic = {}
        arr = [0] * (n+1)
        for i in trust:
            arr[i[1]] += 1
            dic[i[0]] = 1
        for i in range(len(arr)):
            if arr[i] == n-1 and dic.get(i, 0) == 0:
                return i
        return -1

复杂度

时间复杂度On 空间复杂度On

[dtldtt]

2022-04-29

997. 找到小镇的法官

思路

这是一个典型的图的题，但我一开始没想到。 我用的方法是一个集合数组，保存了每个人的被信任的集合，如果结合的个数为N-1（说明除了他自己都相信他），并且另外一个flag标志数组为true，则他是法官，否则没有法官。 该方法时空复杂度都很高，还是要用图的方式。

代码

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
      vector<set<int>> matrix(n);
      vector<bool> flags(n,true);
      for(int i=0;i<trust.size();i++){
        matrix[trust[i][1]-1].insert(trust[i][0]-1);
        flags[trust[i][0]-1]=false;
      }
      int ans=-1;
      for(int i=0;i<n;i++){
        if(matrix[i].size()==n-1 && flags[i]){
          ans=i;
          break;
        }
      }
      return ans==-1?-1:ans+1;
    }
};

复杂度分析

备注

使用图算法的入度出度会好很多。

---

[miss1]

思路

图的基本知识，定义两个数组，记录入度和出度。入度=n-1并且出度=0的点是要寻找的点

代码

var findJudge = function(n, trust) {
  let inArray = new Array(n).fill(0);
  let outArray = new Array(n).fill(0);
  for (let i = 0; i < trust.length; i++) {
    outArray[trust[i][0] - 1] += 1;
    inArray[trust[i][1] - 1] += 1;
  }
  for (let i = 0; i < n; i++) {
    if (inArray[i] === n - 1 && outArray[i] === 0) return i+1;
  }
  return -1;
};

复杂度

time: O(n)

space: O(n)

[LQyt2012]

思路

遍历信任数组即图的边，统计图中节点的度，最后如果有n-1的度节点则返回节点，否则返回-1。

代码

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        # if n == 1 and len(trust) == 0:
        #     return n
        degree = collections.defaultdict(int)
        if len(trust) == 0:
            degree[1] = 0
        for edge in trust:
            degree[edge[0]] -= 1
            degree[edge[1]] += 1
        for key, value in degree.items():
            if value == n-1:
                return key
        return -1

func findJudge(n int, trust [][]int) int {
    degree := map[int]int{}
    if len(trust) == 0 {
        degree[1] = 0
    }
    for _, edge := range trust {
        degree[edge[0]]--
        degree[edge[1]]++
    }
    for key, value := range degree {
        if value == n - 1 {
            return key
        }
    }
    return -1
}

复杂度分析

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

[KWDFW]

Day29

997、找到小镇的法官

javascript #图

思路

1、将题目转化为，找到入度为n-1（除自己），出度为0的编号

2、建立两个数组分别记录每个编号的入度和出度的值

3、遍历trust，记录出度和入度

4、遍历trust，找到符合条件的编号

代码

var findJudge = function(n, trust) {
    let inDegrees=new Array(n+1).fill(0)
    let outDegrees=new Array(n+1).fill(0)
    //初始化存储入度和出度的数组，长度为n+1的原因是编号从1开始，索引0被废弃
    for(let people of trust){
      const x=people[0],y=people[1]
      //x为当前出度的编号，y为当前入度的编号
      inDegrees[y]++
      outDegrees[x]++
      //记录每个编号出度和入度的值
    }
    for(let i=1;i<n+1;i++){
      if(inDegrees[i]===n-1&&outDegrees[i]===0) return i
      //选出出度为0，入度为n-1的编号
    }
    return -1
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[houyanlu]

思路

问题就转化为求图中入度为 n - 1 并且出度为 0的点。 遍历trust数组，构造出度数组和入度数组，最后遍历寻找两个数组中，符合要求的那个下标

代码

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> inDegrees(n + 1); //从1编号所以大小要加1
        vector<int> outDegrees(n + 1);

        for (const auto&item : trust) {
            ++inDegrees[item[1]];
            ++outDegrees[item[0]];
        }

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

复杂度分析

• 时间复杂度：O(n+m), 需要遍历trust数组和第二遍寻找法官的遍历为n
• 空间复杂度：O(n)

[flyzenr]

• 思路

  • 题目两个条件
    • 条件1：除了法官，都信任法官
    • 条件2：法官不信任法官
  • 那么可以利用图数据结构，看图中每个元素的出度和入度。
    • 如果出度是0（条件2），入度是N-1（条件1），那么返回这个元素。
    • 如果不存在，则返回-1

• Code - 图，出度，入度

  -

        class Solution:
            def findJudge(self, n: int, trust: List[List[int]]) -> int:
                if not trust: 
                    if n == 1: return n  
                    else: return -1
                # 存放要维护的（入度-出度）的差值
                count = [0]*(n+1)
                for i,j in trust:
                    # 被信任的元素，入度加1
                    count[i] -= 1
                    # 信任法官的元素，出度减去1
                    count[j] += 1
                print(count)
                # 遍历一遍记录出入度差值的数组，找到满足（N-1）的位置。
                for i in range(len(count)):
                    if count[i] == n-1:
                        return i
                return -1

• 复杂度

  • 时间复杂度: $O(n)$ ，n是数组的长度
  • 空间复杂度 $O(n)$