타운 판사 Leetcode 솔루션 찾기


난이도 쉽게
자주 묻는 질문 아마존
그래프

문제 정책

이 문제에서 우리는 1에서 n까지 라벨이 붙은 n 명의 사람을받습니다. 우리는 또한 2d 정렬 trust [] []는 trust [i] [0] 번째 사람이 1 <= i <trust.length에 대해 trust [i] [0] 번째 사람을 신뢰 함을 보여줍니다.
우리는 다른 사람을 믿지 않고 다른 모든 사람이 그를 신뢰하는“마을 판사”를 찾아야합니다. 그런 사람이 없으면 -1을 반환하고 그렇지 않으면 마을 판사를 반환합니다.

#1

N = 2, trust = [[1,2]]
2

#2

N = 3, trust = [[1,3],[2,3],[3,1]]
-1

#3

N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
3

접근

주어진 시나리오를 사람 a에서 b 로의 간선이 a가 b를 신뢰한다는 것을 보여주는 유 방향 그래프로 취급합시다.
마을 판사는 누구를 신뢰하지 않으며, 마을 판사는 나가는 우위가 없습니다. 다른 모든 n-1 명은 타운 판사를 신뢰하므로 다른 모든 사람으로부터 타운 판사를 향한 총 n-1 인입 에지.
우리는 들어오는 가장자리 수와 나가는 가장자리 수의 차이가 타운 판사에게만 n-1이라는 것을 더 이해할 수 있습니다.
우리가 단순한 사람에 대해 이야기한다면 그는 분명히 min (outgoing edge) = 1을 믿고 다른 모든 사람이 그를 믿더라도 (물론 타운 판사는 그를 믿지 않을 것입니다) 따라서 max (incoming edge) = n-2.
이 사람의 들어오는 가장자리와 나가는 가장자리의 최대 차이는 n-2- (1) = n-3입니다.
또한 타운 심판이 없으면 아무도 들어오는 가장자리와 나가는 가장자리 수 사이의 n-1 차이를 얻을 수 없습니다.

이제 우리의 주된 작업은 차이를 계산하는 것입니다. 즉, 들어오는 가장자리의 수 – 각 사람의 나가는 가장자리의 수입니다. 행 단위로 신뢰 배열을 순회함으로써 그렇게 할 것입니다.
모든 행에는 두 가지 요소가 있습니다. 왼쪽 요소는 신뢰하는 사람이고 오른쪽 요소는 왼쪽 요소가 신뢰하는 사람입니다.
따라서 왼쪽 요소는 오른쪽 요소에서 나가는 가장자리를 갖습니다. 따라서 왼쪽 요소의 차이 값은 1 씩 감소하고 오른쪽 요소의 차이 값은 1 씩 증가합니다.
우리 코드에서는이 작업에 netTrustGains 배열을 사용했습니다. 이 배열의 각 인덱스 i는 i 번째 사람의 차이 값을 보여줍니다.

신뢰 배열을 탐색 한 후 고리 1에서 n까지 각 사람에 대해 차이 값 = n-1을 가진 사람이 있는지 확인하십시오.
그런 사람이 발견되면 우리는 그 사람을 반환하고 그렇지 않으면 -1을 반환합니다.

타운 판사 Leetcode 솔루션 찾기

실시

타운 판사 Leetcode 솔루션 찾기를위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int findJudge(int n, vector<vector<int>>& trust) 
{
    int netTrustGains[n+1];
    memset(netTrustGains, 0, sizeof(netTrustGains));
    for(vector<int>i:trust){
        netTrustGains[i[0]]--;
        netTrustGains[i[1]]++;

    }
    int judge=-1;
    for(int i=1;i<=n;i++){
        if(netTrustGains[i]==n-1){
            judge=i;
        }
    }
    return judge;
}
int main()
{
    int n=3;
    vector<vector<int>>trust
    {
        {1, 3},
        {2, 3}
    };
    cout << findJudge(3,trust);
}
3

마을 판사 Leetcode 솔루션 찾기를위한 Java 프로그램

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int n = 3;
        int[][]trust = {{1,3},{2,3}};
        System.out.println(findJudge(n,trust));
    }
    public static int findJudge(int n, int[][] trust) 
    {
        int[]netTrustGains=new int[n+1];
        for(int[]i:trust){
            netTrustGains[i[0]]--;
            netTrustGains[i[1]]++;
            
        }
        int judge=-1;
        for(int i=1;i<=n;i++){
            if(netTrustGains[i]==n-1){
                judge=i;
            }
        }
        return judge;
    }
}
3

도시 판사 Leetcode 솔루션 찾기를위한 복잡성 분석

시간 복잡성

O (최대 (n, trust.size ())) : 우리는 신뢰 루프를 선형으로 순회했으며 다른 루프는 1에서 n까지 각 사람의 netTrustGains를 확인하기 위해 크기가 n입니다.

공간 복잡성 

의 위에) : 우리는 n + 1 크기의 배열 netTrustGains를 만들었습니다. 따라서 공간 복잡성 O (n).