😆
LeetCode 997. Find the Town Judge
Question
In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.
You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.
Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.
1からnまで、ラベル付けされた人がいるn人の町のtown judgeが特定できるときは、そのラベルを、特定できないときは-1を返しなさいという問題
town judgeの条件は以下であるようだ
- town judgeは誰も信用してない
- town judge以外の人間はtown judgeを信用している
- [ai, bi]の形でaiがbiを信用しているという情報が与えられる
Code
class Solution {
fun findJudge(n: Int, trust: Array<IntArray>): Int {
var subject = Array(n + 1) { 0 }
var trusted = Array(n + 1) { 0 }
for (t in trust) {
val ai = t[0]
val bi = t[1]
subject[ai]++
trusted[bi]++
}
for (i in 1..n) {
if (subject[i] == 0 && trusted[i] == n - 1) return i
}
return -1
}
}
aiが誰かを信じる人数を、subject[ai]、誰かから信じられる人数を、trusted[bi]としそれぞれカウント結果を格納。
subjectとtrustedのインデックスはそれぞれ同一人物の情報を表すので、「town judgeは誰も信用してない」と「town judge以外の人間はtown judgeを信用している」の両方を満たすインデックスをi=1から線形探索する。
配列をMutableMapにすることも試したが対して改善が見られなかった上に、他の解答例も調べたが類似のアプローチしか見つけられなかったのでので撤退。
時間計算量はO(n)のはず。
Profile
- Runtime: 963 ms
- Memory Usage: 101.9 MB
Discussion