د ټاون قاضي لیټکوډ حل ومومئ


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon
ګراف

ستونزه بیان

پدې ستونزه کې ، موږ n خلکو ته ورکړل شوي چې له 1 څخه n پورې لیبل شوي وي. موږ ته 2d هم راکول کیږي سور باور [] [] څرګندوي چې باور [i] [0] th خلک باور لري [i] [1] th خلک د هر 0 <= i <trust.leight لپاره.
موږ باید یو داسې کس ومومو چې د "ښار قاضي" وي څوک چې په نورو خلکو باور نه لري او نور ټول خلک پرې باور لري. که چیرې داسې څوک شتون ونلري نو بیرته -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

او کړنلاره

راځئ چې ورکړل شوې سناریو ته د لارښود ګراف په توګه چلند وکړو په کوم کې چې د یو شخص څخه تر ب څخه د یو څرخ ښیې چې باور لري b.
د ښار قاضي په هیڅ چا باور نه کوي ، نو د ښار قاضي هیڅ تیری نلري. نور ټول N-1 اشخاص د ښار قاضي باور لري ، نو د ټول شخص څخه د ښار قاضي په لور د N-1 راتلونکی څنډه.
موږ نور په دې پوهیږو چې د راتلوونکي څنډو او د وتلو څنډو شمیر ترمنځ توپیر یوازې د ښار قاضي لپاره n-1 دی.
که موږ د یو ساده کس په اړه وغږیږو نو هغه به خامخا د ښار قضاوت باندې باور وکړي پدې ډول من (بهر ته څنډه) = 1 او په غوره حالت کې حتی که ټول نور سړی پر هغه باور ولري (البته د ښار قاضي به پدې باور ونلري) پدې ډول اعظمي (راتلونکی څنډې) = n-2.
د دې شخص لپاره د راتلوونکي او وتلو څنډونو تر منځ ترټولو زیات توپیر د n-2- (1) = n-3 دی.
همدارنګه که چیرې د ښار قاضي شتون ونلري نو بیا هیڅ څوک نشي کولی د راتلوونکي او وتلو څکو تر منځ N-1 توپیر ترلاسه کړي.

اوس ، زموږ اصلي دنده دا ده چې توپیر محاسبه کړئ د بیلګې په توګه د راتلونکو څنډو شمیر - د هر شخص لپاره د وتلو څنډو شمیره. موږ به دا د باور صف صفه وار سره تعقیب کړو.
په هر قطار کې ، دوه عناصر شتون لري. کي element عنصر هغه څوک دی چې باور کوي او ښي عنصر هغه څوک دی چې کی element عنصر باور کوي.
په دې توګه کی left عنصر ښي عنصر ته تلونکي څنډه لري. د همدې لپاره ، د کی left عنصر لپاره د ارزښت ارزښت به د 1 لخوا کم شي او د سم عنصر لپاره ، د 1 لخوا ډیریږي.
زموږ په کوډ کې ، موږ د دې دندې لپاره د نیټ ټرسټ ګینز سرې کارولې. د دې صفونو هر شاخص i د ith شخص لپاره د توپیر ارزښت ښیې.

د باور صف سرغړونې وروسته ، موږ به یو لوپ د هر شخص لپاره له 1 څخه n پورې او وګورئ چې آیا کوم شخص د توپیر ارزښت لري = n-1.
که چیرې داسې یو څوک وموندل شي نو موږ به هغه بیرته راستون کړو او موږ به بیرته راستون کړو -1.

د ټاون قاضي لیټکوډ حل ومومئ

تطبیق

د ټاون قاضي لیټکوډ حل موندلو لپاره 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

د ټاون قاضي لیټکوډ حل موندل لپاره جاوا برنامې

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

د ټاون قاضي لیټکوډ حل موندل لپاره د پیچلتیا تحلیلونه

د وخت پیچلتیا

O (اعظمي (ن، ټرسټ سایز ())): موږ د اعتبار لوپ په ساده ډول تعقیب کړی او بل لوپ یې د n اندازې دی چې د هر وګړي لپاره له 1 څخه تر n پورې د नेट ټرسټ ګینز چیک کول دي.

د ځای پیچلتیا 

O (n): موږ د N + 1 د اندازې یو آرټ نیټ ټرسټ ګینونه رامینځته کړی پدې توګه د ځای پیچلتیا O (n).