ટાઉન જજ લીટકોડ સોલ્યુશન શોધો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન
ગ્રાફ

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને 1 થી n ના લેબલવાળા n લોકો આપવામાં આવે છે. અમને પણ 2 ડી આપવામાં આવે છે એરે વિશ્વાસ [] [બતાવે છે કે વિશ્વાસ [i] [0] મી લોકો વિશ્વાસ પર વિશ્વાસ રાખે છે [i] [1] મી દરેક લોકો માટે વિશ્વાસ [i] [0] મી લોકો વિશ્વાસ [લંબાઈ].
આપણે એક એવી વ્યક્તિને "ટાઉન જજ" શોધી કા whoવાની છે કે જે બીજા કોઈપણ લોકો પર વિશ્વાસ ન કરે અને બીજા બધા લોકો તેના પર વિશ્વાસ રાખે છે. જો આવી કોઈ વ્યક્તિ અસ્તિત્વમાં ન હોય તો પાછા ફરવું -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.
આ વ્યક્તિ માટે આવતા અને જતા ધાર વચ્ચેનો મહત્તમ તફાવત એ n-2- (1) = n-3 છે.
ઉપરાંત જો ત્યાં કોઈ ન્યાયાધીશ ન હોય તો પછી કોઈ પણ વ્યક્તિ ઇનકમિંગ અને આઉટગોઇંગ ધારની સંખ્યા વચ્ચેનો n-1 તફાવત પ્રાપ્ત કરી શકશે નહીં.

હવે, અમારું મુખ્ય કાર્ય એ તફાવતની ગણતરી કરવાનું છે એટલે કે આવતા ધારની સંખ્યા - દરેક વ્યક્તિ માટે આઉટગોઇંગ ધારની સંખ્યા. અમે ટ્રસ્ટને એરે પંક્તિ મુજબ ટ્ર traર્સ કરીને કરીશું.
કોઈપણ પંક્તિમાં, ત્યાં બે તત્વો હોય છે. ડાબું તત્વ તે છે કે જે વિશ્વાસ કરે છે અને જમણો તત્વ તે છે જેનો ડાબી તત્વ વિશ્વાસ કરે છે.
આમ ડાબી તત્વ જમણી તત્વની બહાર જતા ધાર છે. તેથી, ડાબી તત્વ માટેના તફાવત મૂલ્યમાં 1 અને જમણા તત્વ માટે, 1 દ્વારા ઘટાડો થશે.
અમારા કોડમાં, અમે આ કાર્ય માટે નેટટ્રસ્ટગાઇન્સ એરેનો ઉપયોગ કર્યો છે. આ એરેનો દરેક અનુક્રમણિકા આઇથ વ્યક્તિ માટેનો તફાવત મૂલ્ય બતાવે છે.

ટ્રસ્ટ ટ્રાય ટ્રસ્ટ કર્યા પછી, અમે એક ચલાવીશું લૂપ 1 થી n સુધીના દરેક વ્યક્તિ માટે અને તપાસો કે કોઈ પણ વ્યક્તિમાં તફાવત મૂલ્ય = n-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 થી n સુધીની દરેક વ્યક્તિ માટે નેટટ્રસ્ટગ toન્સને તપાસવા માટે બીજી લૂપ કદ n ની છે.

અવકાશ જટિલતા 

ઓ (એન): આપણે n + 1 સાઇઝના એરે નેટટ્રસ્ટગsન્સ બનાવ્યા છે જેથી સ્પેસ જટિલતા O (n).