Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/997.html
In a town, there are N people labelled 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 trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.
If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.
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
Example 4:
Input: N = 3, trust = [[1,2],[2,3]]
Output: -1
Example 5:
Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3
Constraints:
1 <= N <= 1000
0 <= trust.length <= 10^4
trust[i].length == 2
trust[i] are all different
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N
Algorithm 1
This question is similar to previous question which is Find the Celebrity. The question is that everyone knows celebrities, but celebrities don’t know anyone. And here is that the judge does not believe in anyone, and everyone believes in the judge. The difference is that the data structure is different. The celebrity way is to give an API to judge whether they know or not, and here is a trust array, then the solution is It’s slightly different. Since trust has a direction, it is a directed graph. Because the judge does not trust anyone, he has no degree. If everyone trusts him, the degree is full. The simplest and most direct method is to count the out-degree and in-degree of each node, and then find out the node whose out-degree is 0 and in-degree is N-1. Please refer to the following code:
Code 1
C++
class Solution {
public:
int findJudge(int N, vector<vector<int>>& trust) {
vector<int> in(N + 1), out(N + 1);
for (auto a : trust) {
++out[a[0]];
++in[a[1]];
}
for (int i = 1; i <= N; ++i) {
if (in[i] == N - 1 && out[i] == 0) return i;
}
return -1;
}
};
Algorithm 2
If you have not come up with a solution for the out-degree and in-degree of the directed graph, you can also use the following method. The idea is this. Since the judge will not trust anyone, the person in the previous position is definitely not the judge, so use A HashSet to save all people who believe in others, and then use a HashMap to build a set of a certain person and everyone who trusts that person, then as long as you find out who is not in the HashSet, and there are N-1 people who trust him, then The person must be a judge. In fact, it is essentially the same as the above solution. The code is as follows:
Code 2
C++
class Solution {
public:
int findJudge(int N, vector<vector<int>>& trust) {
unordered_set<int> st;
unordered_map<int, vector<int>> beTrustedMap;
for (auto &a : trust) {
st.insert(a[0]);
beTrustedMap[a[1]].push_back(a[0]);
}
for (int i = 1; i <= N; ++i) {
if (st.count(i)) continue;
if (beTrustedMap[i].size() == N - 1) return i;
}
return -1;
}
};
-
class Solution { public int findJudge(int N, int[][] trust) { int[][] trustArray = new int[N][2]; for (int[] curTrust : trust) { int person1 = curTrust[0] - 1, person2 = curTrust[1] - 1; trustArray[person1][0]++; trustArray[person2][1]++; } for (int i = 0; i < N; i++) { if (trustArray[i][0] == 0 && trustArray[i][1] == N - 1) return i + 1; } return -1; } } ############ 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; } } -
// OJ: https://leetcode.com/problems/find-the-town-judge/ // Time: O(N) // Space: O(N) class Solution { public: int findJudge(int N, vector<vector<int>>& trust) { vector<int> indegree(N + 1), outdegree(N + 1); for (auto &t : trust) { outdegree[t[0]]++; indegree[t[1]]++; } int judge = -1; for (int i = 1; i <= N; ++i) { if (indegree[i] != N - 1 || outdegree[i] != 0) continue; if (judge != -1) return false; judge = i; } return judge; } }; -
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 ############ # 997. Find the Town Judge # https://leetcode.com/problems/find-the-town-judge/ class Solution: def findJudge(self, n: int, trust: List[List[int]]) -> int: trusted = [0] * (n + 1) trust_other = [0] * (n + 1) for u, v in trust: trusted[v] += 1 trust_other[u] += 1 for i in range(1, n + 1): if trusted[i] == n - 1 and trust_other[i] == 0: return i return -1 -
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 } -
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; }