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

[ccslience]

• 1.思路: 法官被信任n-1次, 且不信任任何人;

• 2.时间复杂度:O(n),空间复杂度:O(n).

• 3.也可以用两个数组分别表示出度和入度, 最终出度为0, 入度为n-1的即为法官.

  int findJudge(int n, vector<vector<int>>& trust)
  {
      unordered_map<int, int> count;
      unordered_map<int, int> t;
      for(auto it: trust)
      {
          count[it[1]]++;
          t[it[0]] = 1;
      }
      for(auto it : count)
      {
          if(it.second == n - 1 && t.find(it.first) == t.end())
              return it.first;
      }
      return -1;
  }

[yopming]

// Graph problem.
// Convert all people to one node in the graph, then judge will the one whose in degree is n-1 and whose out degree is 0. 
// (If we define a trusts b as one directed connection from a to b, a->b).

// Time: O(n)
// Space: O(n)

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

[MichaelXi3]

Idea

利用”Graph”的特性,发现Judge一定为”in_degree-out_degree=n-1”的点。 历遍并计算每一个点的in_degree-out_degree，若有点的值为n-1，则为judge。

Code

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] people = new int[n+1];

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

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

[flaming-cl]

class Solution {
    // T: O(m + n)
    // S: O(n)
    // 受到的信任：入度 in
    // 给出的信任：出度 out

    // 法官：
    // 信任：0 次，被信任 n - 1 (自己) 次
    // 出度：0，入度：n - 1
    public int findJudge(int n, int[][] trust) {
        int res = -1;
        int[] in = new int[n + 1]; // 入度，被信任
        int[] out = new int[n + 1]; // 出度，给出信任
        for (int[] t : trust) {
            // t[0] 给出信任 -> out
            // t[1] 被信任 -> in
            out[t[0]]++;
            in[t[1]]++;
        }
        for (int i = 1; i<= n; i++) {
            if (in[i] == n - 1 && out[i] == 0) {
                res = i;
                break;
            }
        }
        return res;
    }
}

[laofuWF]

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

        for truster, trustee in trust:
            trusted_count[truster - 1] -= 1
            trusted_count[trustee - 1] += 1

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

        return -1            

[thinkfurther]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        t0 = collections.defaultdict(int)
        t1 = collections.defaultdict(int)

        for connection in trust:
            t0[connection[0]] += 1
            t1[connection[1]] += 1

        result = -1
        for i in range(1,n+1):
            if t1[i] == n - 1 and t0[i] == 0:
                result = i
                break

        return result

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

[lbc546]

Judge when out degree is 0 and in degree is n - 1

Python solution

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if len(trust) < n - 1:
            return -1
        degrees = [0] * n
        for a, b in trust:
            degrees[a - 1] -= 1
            degrees[b - 1] += 1
        for i, degree in enumerate(degrees):
            if degree == n - 1:
                return i + 1
        return -1

Complexity

O(n) Python SLOW

[djd28176]

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

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

[XingZhaoDev]

class Solution {
    func findJudge(_ n: Int, _ trust: [[Int]]) -> Int {

        var indegrees = Array(repeating:0, count: n + 1)
        var outdegrees = Array(repeating: 0, count: n + 1)

        for edge in trust {
            indegrees[edge[1]] += 1
            outdegrees[edge[0]] += 1
        }
        print(indegrees)
        print(outdegrees)

        for i in 1...n {
            if indegrees[i] == n-1 && outdegrees[i] == 0 {
                return i
            }
        }
        return -1
    }
}

[haoyangxie]

code

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) {
            indegree[edge[1]]++;
            outdegree[edge[0]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == n - 1 && outdegree[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}

complexity

Time: O(n) Space: O(n)

[Cusanity]

Solution

Language: Java

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

[dereklisdr]

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

Time complexity: O(n+m) Space complexity: O(n)

[shiyishuoshuo]

code

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

[ceramickitten]

思路

入度为n - 1，出度为0

代码

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

复杂度分析

• Time: O(n)
• Space: O(n)

[Tomtao626]

思路

• 逻辑题 有人相信iarr[i]++，i相信某人arr[i]--，如果满足法官的话arr[i]必须等于n - 1

代码

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

复杂度

• 时间: O(N)
• 空间: O(N)

[Whisht]

思路

根据 trust 数组构建图，法官即入度为0，出度为 n-1 的结点。

代码

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        matrix = [[0]*n for _ in range(n)]
        for fr, to in trust:
            matrix[fr-1][to-1]=1

        matrix_t = list(zip(*matrix))

        for i in range(n):
            degree_out = sum(matrix[i])
            degree_in = sum(matrix_t[i])
            if  degree_in == n-1 and degree_out==0:
                return i+1
        return -1

[ashleyyma6]

Idea

• Mark people who trust someone else
• Count how many people trust the person who do not trust anyone else
• If the trust count is equal to n-1, that person is judge

Code

public int findJudge(int n, int[][] trust) {
    if(n==1){
        return 1;
    }
    int[] trusted = new int[n];
    for(int[] arr: trust){
        trusted[arr[0]-1]=-1;
        if(trusted[arr[1]-1]!=-1){
            trusted[arr[1]-1]+=1;
        }
    }
    for(int i =0;i<n;i++){
        if(trusted[i]==(n-1)){
            return i+1;
        }
    }
    return -1;
}

Complexity Analysis

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

[mannnn6]

class Solution:
    def findJudge(self, N, trust):
        if not len(trust) and N < 2: return 1

        count = [0] * (N + 1)
        for i, j in trust:
            count[i] -= 1
            count[j] += 1
        v = max(count)
        return count.index(v) if v == N - 1 else -1

[maoting]

思路：

遍历trust, 记录每个节点的出度和入度，对于ai 的人信任编号为 bi，ai的出度是1，bi的入度为1。 判断是否为法官：入度为n-1, 出度为0

代码

var findJudge = function(n, trust) {
    let len = trust.length;
    // 1[] => 1
    // 2[] => -1
    if (!len) return n === 1 ? 1 : -1;
    if (n-1 > len) return -1;
    let hash = {}
    for(let i = 0; i<len; i++) {
        // ai 的人信任编号为 bi 
        let [ai, bi] = trust[i];
        if (!hash[ai]) {
            // 设置出度（ [0, 1]：入度，出度）
            hash[ai] = [0, 1];
        }
        else {
            // 出度
            hash[ai][1] += 1;
        }
        if (!hash[bi]) {
            // 设置入度（ [1, 0]：入度，出度）
            hash[bi] = [1, 0];
        }
        else {
            // 入度
            hash[bi][0] += 1;
        }
    }
    for(let i = 1; i <= n; i++) {
        // 法官：入度为n-1, 出度为0
        if (hash[i] && hash[i][0] === n-1 && !hash[i][1]) {
            return i;
        }
    }
    return -1;
};   

// 官方题解：用两个数组存放入度和出度，并设着了初始值。保证了1[] => 1
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)

[kernelSue]

class Solution {
    public int findJudge(int n, int[][] trust) {
        if(n == 1)  return 1;
        if(trust.length < n-1)  return -1;
        if(n == 2){
            if(trust.length == 1)  return trust[0][1];
            else  return -1;
        }

        int[] trustValue = new int[n];
        for(int i = 0; i < trust.length; i++){
            trustValue[trust[i][0]-1]--;
            trustValue[trust[i][1]-1]++;
        }
        int judge = -1;
        for(int i = 0; i < trustValue.length; i++){
            if(trustValue[i] == n-1){
                judge = i+1;
                break;
            }
        }
        return judge;
    }
}

[nikojxie]

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

[Tlntin]

题目链接

• 链接

  代码

  class Solution {
  public:
  int findJudge(int n, vector<vector<int>>& trust) {
  // 根据题目定义，找到一个入度为n-1,出度为0的节点，如果找不到，则返回
  // 加入极限条件
  if (!trust.size() && n == 1) {
    return 1;
  }
  std::map<int, int> dict1; // 记录入度
  std::map<int, int> dict2; // 记录出度
  for (auto const & data: trust) {
    ++dict1[data[1]];
    ++dict2[data[0]];
  }
  for (auto const & item: dict1) {
    if (item.second == n - 1 && !dict2.count(item.first)) {
      return item.first;
    }
  }
  return -1;
  }
  };

优化思路

• dict貌似需要重新插入，而且效果还不如unorder_map, 改成用vector映射貌似更好，保证每个人都有默认值。
• 由于元素最大为n,所以vector数组size应该为n+1, 0索引可以储存入度为n-1的元素索引，减少一次for循环。
• 出度其实可以不用记录，如果有出度，直接就将入度改成-2n即可。

class Solution {
public:
  int findJudge(int n, vector<vector<int>>& trust) {
    // 根据题目定义，找到一个入度为n-1,出度为0的节点，如果找不到，则返回
    std::vector<int> in_v(n + 1, 0); // 记录入度
    // 定义一个初始值，用于满足极限条件trust.size() = 0, n = 1
    in_v[0] = 1;
    // std::vector<int> out_v(n + 1, 0); // 记录出度
    int n2 = n * 2;
    for (auto const & data: trust) {
      ++in_v[data[1]];
      in_v[data[0]] = -n2;
      if (in_v[data[1]] == n - 1) {
        in_v[0] = data[1];
      }
    }
    if (in_v[in_v[0]] == n - 1) {
      return in_v[0];
    } else{
      return -1;
    }
  }
};

复杂度

• 时间：O(n)
• 空间：O(n)

结果

[cyang258]

thoughts

we convert each person as node in graph, we convert "a trust b" to "there is a directed edge from a to b", then a would increase out_degree by one and b would increase in_degree by one. With the given information, we know town judge trust no one, thus out_degree would be 0 and judge trusted by everyone except himself, so in_degree would be n-1. we use two arrays to store the in_degree and out_degree then find one that meet the condition

public int findJudge(int n, int[][] trust) {
        // 转化为图 in-degree and out-degree
        // we can see [a,b] means a->b, so a out-degree++ and b in-degree++
        // since everyone trust town judge and town judge trust no one, so town judge in-degree should be n-1 and out-dgree should be 0
        int[] in_degree = new int[n+1];
        int[] out_degree = new int[n+1];
        for(int i = 0; i < trust.length; i++){
            int in = trust[i][1];
            int out = trust[i][0];
            in_degree[in] = in_degree[in] + 1;
            out_degree[out] = out_degree[out] + 1;
        }
        for(int i = 1; i < n + 1; i++){
            if(in_degree[i] == n - 1 && out_degree[i] == 0) return i;
        }
        return -1;
}

Time Complexity: O(N)

Space Complexity: O(N)

[Serena9]

思路

根据trust建图，两个数组分别存放入度和出度，a若指向b，表明a信任b，最后找到入度为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 i, j in trust:
            in_degree[j] += 1
            out_degree[i] += 1
        for x in range(1, n+1):
            if in_degree[x] == n-1 and out_degree[x] == 0:
                return x
        return -1

复杂度分析

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

[LiquanLuo]

/***
Solution:
1. convert trust into a hash map
A->B   ==>  B: set<>{A,}   O(n)

another set<int> to note down who has trust, because "The town judge trusts nobody."
we need to make sure the judge does not have trust

2. for key in hash map
check its set.size() == n O(n)

Time: O(n)
Space: O(n)

***/

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        if (trust.size() == 0 && n == 1) {
            if (n == 1) {
                return 1;
            }
            else {
                return -1;
            }
        }
        unordered_map<int, unordered_set<int>> m;
        unordered_set<int> has_trust;
        for (auto t : trust) {
            if (m.find(t[1]) != m.end()) {
                m[t[1]].insert(t[0]);
            }
            else {
              unordered_set<int> s{t[0]};
              m[t[1]] = s;  
            }

            has_trust.insert(t[0]);
        }

        for (auto iter : m) {
            if (iter.second.size() == n - 1 && 
                has_trust.find(iter.first) == has_trust.end()) {
                return iter.first;
            }

            // cout << iter.first << " : " << iter.second.size() << endl;
        }

        return -1;
    }
};

[luhaoling]

Idea

使用图中的入度和出度解题，如果一个点的入度和出度等于n-1，则该点所对应的人是小镇法官

Code

public class day29 {
    public int findJudge(int n, int[][] trust) {
        int[] count=new int[n+1];
        for(int[] edge:trust){
            int x=edge[0];
            int y=edge[1];
            ++count[y];
            --count[x];//标记，判断是否满足条件1，如果法官信任其他人，那么这个点的信任值会达不到n-1
        }
        System.out.println(count);
        for(int i=1;i<n+1;i++){
            if(count[i]==n-1){//是否满足第二个条件
                return i;
            }
        }
        return -1;
    }
}

[mo-xiaoxiu]

思路

• 有向图：每个居民都是一个节点，信任谁则指向谁，表示出度；谁被信任则被（边）指向，表示入度
• 小镇法官：两个条件的转换 = 出度为0 + 入度为n - 1（除他自己以外）

具体实现

• 准备两个数组分别统计每个节点额入度和出度
• 遍历编号，找到同时满足小镇法官两个条件的编号返回

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> inDegree(n + 1); //统计入度
        vector<int> outDegree(n + 1); //统计出度
        for(auto& vec: trust) {
            inDegree[vec[1]]++;
            outDegree[vec[0]]++;
        }

        //小镇法官：入度为n - 1，出度为0
        for(int i = 1; i < n + 1; i++) {
            if(inDegree[i] == n - 1 && outDegree[i] == 0)
                return i;
        }

        return -1;
    }
};

空间优化

• 使用一个数组同时统计入度和出度，当节点有被指向时，+1；该节点指向别的节点时，-1
• 由于法官不信任任何人，所以出度为0，入度还是为n - 1，所以该位置数组元素为n - 1

具体实现

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> degree(n + 1);
        for(auto& vec: trust) {
            degree[vec[1]]++;
            degree[vec[0]]--;
        }

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

        return -1;
    }
};

[xi2And33]

var findJudge = function (n, trust) {
  const count = new Array(n + 1).fill(0);
  for (const edge of trust) {
    const x = edge[0];
    const y = edge[1];
    count[y]++;
    count[x]--;
  }
  for (let i = 1; i <= n; ++i) {
    if (count[i] === n - 1) {
      return i;
    }
  }
  return -1;
};

[UCASHurui]

思路

---

统计所有节点的出度和入度，法官节点出度为0，入度为n-1

代码

---

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        indegree = [0] * (n + 1)
        outdegree = [0] * (n + 1)
        for a, b in trust:
            outdegree[a] += 1
            indegree[b] += 1
        ans = []
        for i in range(1, n+1):
            if outdegree[i] == 0 and indegree[i] == n-1:
                ans.append(i)
        if len(ans) != 1: return -1
        return ans[0]

复杂度分析

---

• 时间复杂度：O(M),M为边的数量
• 空间复杂度：O(N)

[AtaraxyAdong]

思路

朴实的思路

建立一张“信任图”，每个人信任的数量和被信任的数量。

先遍历 trust ，完善“信任图”的信息，再遍历“信任图”，找到入度为0，出度为 n-1 的值，就是目标值；若没有则没有法官，返回-1

代码

class Solution {
    public int findJudge(int n, int[][] trust) {

        // int[personIndex] == int[][] trust num, be trusted num
        int[][] trustGraph = new int[n][2];

        for (int i = 0; i < trust.length; i++) {
            int person = trust[i][0];
            int trustPerson = trust[i][1];

            trustGraph[person - 1][0]++;
            trustGraph[trustPerson - 1][1]++;
        }
        for (int i = 0; i < trustGraph.length; i++) {
            // 不相信任何人 其他人都相信他
            if (trustGraph[i][0] == 0 && trustGraph[i][1] == n - 1) {
                return i+1;
            }
        }

        return -1;
    }
}

复杂度分析

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

[luckyoneday]

思路

第一次做图的题...

代码 js

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

    for (let i = 0; i < trust.length; i++) {
         const first= trust[i][0];
        const second = trust[i][1];
        count[second]++;
        count[first]--;
    }

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

    return -1;
};

复杂度

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

[nehchsuy]

思路

哈希表

代码

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        io = {}
        oi = {}

        for i in range(1, n + 1):
            io[i] = 0
            oi[i] = 0

        for pair in trust:
            i, j = pair[0], pair[1]
            io[i] += 1
            oi[j] += 1

        for i in range(1, n + 1):
            if oi[i] != n - 1:
                continue
            if io[i] == 0 :
                return i

        return -1

[youzhaing]

题目: 997. 找到小镇的法官

思路

用图的入度、出度

python代码

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

复杂度：

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

[wzasd]

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

[testplm]

class Solution(object):
    def findJudge(self, n, trust):
        trusted = [0] * (n + 1)
        for (a,b) in trust:
            trusted[a] -= 1
            trusted[b] += 1
        for i in range(1, n + 1):
            if trusted[i] == n - 1:
                return i
        return -1

[xixiao51]

Idea

Graph - build a single Array with the result of indegree - outdegree for each person

Code

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

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

        return -1;
    }
}

Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(n)

[herbertpan]

code

class Solution {
    public int findJudge(int n, int[][] trust) {

        int[] indegrees = new int[n + 1];

        for (int[] pair : trust) {
            indegrees[pair[0]]--;
            indegrees[pair[1]]++;
        }

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

[jackgaoyuan]

func findJudge(n int, trust [][]int) int { out := make(map[int]int) in := make(map[int]int) // { index : count } res := -1 for _, value := range trust { out[value[0]] += 1 in[value[1]] += 1 } for pIndex, count := range in { if count == n - 1 && out[pIndex] == 0 { res = pIndex } } return res }

[zch-bit]

Day 29

func findJudge(n int, trust [][]int) int {
    if n == 1 {
        return 1
    }

    trusteeH := map[int]int{}
    trustSrcH := map[int]int{}
    for _, t := range trust {
        trustSrcH[t[0]]++
        trusteeH[t[1]]++
    }

    nM1 := n - 1
    for k := range trusteeH {
        if trusteeH[k] == nM1 && trustSrcH[k] == 0 {
            return k
        }
    }
    return -1
}

[lzyxts]

Idea

• 法官只可能是trust[i][0]没有出现的人，用set记录出现过的人。
• hash table记录相信 i 的人员名单。遍历set中没有出现的人j，如果hash[j]是1-n只缺少j，那么此人就是法官。这里用数组总和计算，好像没有用到图

Code

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

        store = defaultdict(list)
        people = set()

        for lst in trust:
            if lst[0] not in people:
                people.add(lst[0])
            store[lst[1]].append(lst[0])

        i = 1
        while i <= n:
            if i not in people:
                judge = (n+1)*n/2 - i
                if len(store[i]) == n-1 and sum(store[i])==judge:
                    return i
            i+=1

        return -1

Complexity

• Time：O(n)
• Space：O(n)

[smz1995]

思路

• 图；法官被信任n-1次，信任他人0次

代码

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

[xxoojs]

代码

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
*/
var findJudge = function(n, trust) {
    const count = new Array(n).fill(0);
    trust.forEach(([pNum, tNum]) => {
        count[pNum - 1]--;
        count[tNum - 1]++;
    });

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

    return -1;
};

[ZOULUFENG]

language:python

---

Idea：there is no idea, just use simple way to solve this problem step by step

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

    for i in a_dict.keys():
        if a_dict[i] == n - 1 and i not in a_list:
            return i
    return -1

time:$O(n)$
space:$O(n)$

[hydelovegood]

思路

使用两个数据记录信任他人和被他人信任

代码

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

        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

复杂度

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

[Irenia111]

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

[tian-pengfei]

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

        //寻找出度为0入度为n-1的节点。

        vector<int> c(n+1,0);

        vector<int> r(n+1,0);

        for (auto &tr:trust){

            c[tr[0]]++;
            r[tr[1]]++;
        }

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

        return -1;

    }
};

[phoenixflyingsky]

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

[suukii]

• Time: $O(N)$

• Space: $O(N)$

  class Solution {
  public:
  int findJudge(int n, vector<vector<int>>& trust) {
      vector<int> in(n + 1, 0);
      vector<int> out(n + 1, 0);
  
      for (const auto& t : trust) {
          in[t[1]]++;
          out[t[0]]++;
      }
  
      // 寻找出度为0，入度为n-1的节点
      for (int i = 1; i < n + 1; i++)
          if (out[i] == 0 && in[i] == n - 1)
              return i;
  
      return -1;
  }
  };

[adamw-u]

1.1 自己的解有问题，没有考虑到1,[]，情况

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

[bulingbulingbuling]

出度入度

将数组每一下项看成指向边 起点记出度数组里 终点进入度数组里 遍历数组 满足出度0 入度n-1 当前位置就是法官

var findJudge = function(n, trust){
  let inArr = new Array(n + 1).fill(0)
  let outArr = new Array(n + 1).fill(0)
  for (let i = 0; i < trust.length; i++) {
    const [outI, inI] = trust[i]
    outArr[outI] += 1
    inArr[inI] += 1
  }
  for (let j = 1; j < n + 1; j++) {
    if(outArr[j] === 0 && inArr[j] === n - 1)
    return j
  }
  return -1
};