997.Find the Town Judge

tags: Easy,Array,Hash Table,Graph

997. Find the Town Judge

題目描述

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:

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 an array trust where trust[i] = [$a_i$, $b_i$] representing that the person labeled $a_i$ trusts the person labeled $b_i$.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

範例

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

Constraints:

• 1 <= n <= 1000
• 0 <= trust.length <= 10⁴
• trust[i].length == 2
• All the pairs of trust are unique.
• $a_i$ != $b_i$
• 1 <= $a_i$, $b_i$ <= n

解答

C++

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

Yen-Chi ChenTue, Jan 24, 2023

Reference

回到題目列表