टाउन जज लेटकोड सॉल्यूशन का पता लगाएं


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना
ग्राफ

समस्या का विवरण

इस समस्या में, हमें n को 1 से n तक लेबल वाले लोग दिए गए हैं। हमें 2 डी भी दिया जाता है सरणी विश्वास [] [] दर्शाता है कि विश्वास [i] [०] वें लोग विश्वास पर भरोसा करते हैं [i] [१] वें लोग प्रत्येक ० <= i <ट्रस्ट पर भरोसा करते हैं।
हमें एक ऐसा व्यक्ति "टाउन जज" खोजना होगा जो किसी अन्य लोगों पर भरोसा नहीं करता है और अन्य सभी लोग उस पर भरोसा करते हैं। यदि ऐसा कोई व्यक्ति मौजूद नहीं है, तो -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 तक की एक किनारे से पता चलता है कि एक ट्रस्ट b।
एक नगर न्यायाधीश किसी पर भरोसा नहीं करता है, शहर न्यायाधीश के पास कोई आउटगोइंग एज नहीं है। सभी अन्य n-1 व्यक्ति शहर के न्यायाधीश पर भरोसा करते हैं, इस प्रकार कुल n-1 आने वाले सभी लोगों से शहर के न्यायाधीश की ओर आता है।
हम आगे समझ सकते हैं कि आने वाले किनारों की संख्या और आउटगोइंग किनारों की संख्या के बीच अंतर केवल नगर न्यायाधीश के लिए एन -1 है।
अगर हम एक साधारण व्यक्ति के बारे में बात करते हैं, तो वह निश्चित रूप से शहर के न्यायाधीश पर भरोसा करेगा, इस तरह से मिनट (आउटगोइंग किनारों) = 1 और सबसे अच्छी स्थिति में, भले ही अन्य सभी व्यक्ति उस पर भरोसा करें (बेशक शहर के न्यायाधीश उस पर भरोसा नहीं करेंगे) इस प्रकार अधिकतम (आने वाले किनारों) = एन -2।
इस व्यक्ति के लिए आने वाले और बाहर जाने वाले किनारों के बीच अधिकतम अंतर n-2- (1) = n-3 है।
इसके अलावा अगर कोई नगर न्यायाधीश नहीं है तो कोई भी व्यक्ति आने वाले और बाहर जाने वाले किनारों की संख्या के बीच n-1 अंतर को प्राप्त नहीं कर सकता है।

अब, हमारा मुख्य कार्य अंतर की गणना करना है अर्थात आने वाले किनारों की संख्या - प्रत्येक व्यक्ति के लिए आउटगोइंग किनारों की संख्या। हम विश्वास सरणी पंक्ति-वार ट्रेस करके ऐसा करेंगे।
किसी भी पंक्ति में, दो तत्व होते हैं। लेफ्ट एलिमेंट वह है जो ट्रस्ट करता है और राइट एलिमेंट जिसे लेफ्ट एलिमेंट ट्रस्ट करता है।
इस प्रकार बाएं तत्व में आउटगोइंग एज टू राइट एलिमेंट है। इसलिए, बाएं तत्व के लिए अंतर मूल्य 1 से कम हो जाएगा और सही तत्व के लिए, 1 से बढ़ेगा।
हमारे कोड में, हमने इस कार्य के लिए netTrustGains सरणी का उपयोग किया है। इस एरे के प्रत्येक इंडेक्स I को ith व्यक्ति के लिए अंतर मान दिखाता है।

विश्वास सरणी के बाद, हम एक चलाएंगे पाश प्रत्येक व्यक्ति के लिए 1 से n तक और जाँच करें कि क्या किसी व्यक्ति का अंतर मान = n-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, Trust.size) ()): हमने ट्रस्ट लूप को रैखिक रूप से ट्रेस किया है और प्रत्येक व्यक्ति के लिए 1 से n तक नेटट्रस्टगंज की जांच करने के लिए एक और लूप आकार n है।

अंतरिक्ष जटिलता 

पर) : हमने आकार n + 1 का एक सरणी netTrustGains बनाया है, इस प्रकार अंतरिक्ष जटिलता O (n) है।