Пронађите решење градског судије Леетцоде


Ниво тешкоће Лако
Често питани у амазонка
Графикон

Изјава о проблему

У овом проблему добићемо н људи означених од 1 до н. Такође смо добили 2д поредак повјерење [] [] показује да повјерење [и] [0] тх људи вјерује повјерење [и] [1] тх људи за сваку 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

Приступ

Третирајмо дати сценарио као усмерени граф у коме ивица од особе а до б показује да поверење б.
Градски судија тако не верује никоме, градски судија нема одлазеће предности. Све остале особе од н-1 тако верују градском судији, укупно н-1 долазних ивица према градском судији од свих осталих особа.
Даље можемо разумети да је разлика између броја долазних ивица и броја одлазних ивица н-1 само за градског судију.
Ако говоримо о једноставној особи, он ће сигурно веровати градском судији, тако да је мин (одлазне ивице) = 1, ау најбољем случају чак и ако му верује сва друга особа (наравно, градски судија му неће веровати), дакле мак (долазне ивице) = н-2.
Максимална разлика између долазних и одлазних ивица за ову особу је н-2- (1) = н-3.
Такође, ако не постоји градски судија, нико не може постићи н-1 разлику између броја долазних и одлазних ивица.

Сада је наш главни задатак израчунати разлику, односно број долазних ивица - број одлазних ивица за сваку особу. То ћемо учинити тако што ћемо низ редова поверења превалити низом поверења.
У било којем реду постоје два елемента. Леви елемент је онај коме верује, а десни елемент коме леви елемент верује.
Тако леви елемент има излазну ивицу удесни елемент. Стога ће се вредност разлике за леви елемент смањити за 1, а за десни елемент повећати за 1.
У нашем коду смо за овај задатак користили низ нетТрустГаинс. Сваки индекс и овог низа приказује вредност разлике за и-ту особу.

Након преласка преко низа поверења, покренућемо а петља за сваку особу од 1 до н и проверите да ли нека особа има вредност разлике = н-1.
Ако се таква особа пронађе, ми ћемо је вратити, вратићемо -1.

Пронађите решење градског судије Леетцоде

Имплементација

Ц ++ програм за проналажење решења градског судије Леетцоде

#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

Јава програм за проналажење решења градског судије Леетцоде

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

Анализа сложености за проналажење решења градског судије Леетцоде

Сложеност времена

О (мак (н, труст.сизе ())): Линеарно смо прешли петљу поверења, а друга петља је величине н да бисмо проверили нетТрустГаинс за сваку особу од 1 до н.

Сложеност простора 

На) : Створили смо низ нетТрустГаинс величине н + 1, па је сложеност простора О (н).