راه حل شهر قاضی Leetcode را پیدا کنید


سطح دشواری ساده
اغلب در آمازون
گراف

بیان مسأله

در این مشکل ، به ما n نفر داده می شود که از 1 تا n برچسب گذاری شده اند. همچنین به ما 2d داده می شود صف اعتماد [] [] نشان می دهد که اعتماد [من] [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

روش

بیایید سناریوی داده شده را به عنوان یک نمودار کارگردانی در نظر بگیریم که در آن یک لبه از شخص a تا b نشان می دهد که a اعتماد b را دارد
بنابراین قاضی شهر به کسی اعتماد ندارد ، قاضی شهر فاقد امتیاز خروجی است. بنابراین همه n-1 افراد دیگر به قاضی شهر اعتماد می کنند ، از طرف دیگر تعداد n-1 نسبت به قاضی شهر کاملاً قابل قبول است.
ما همچنین می توانیم درک کنیم که تفاوت بین تعداد لبه های ورودی و تعداد لبه های خروجی فقط برای قاضی شهر n-1 است.
اگر در مورد یک فرد ساده صحبت کنیم ، مطمئناً او به قاضی شهر اعتماد خواهد کرد بنابراین حداقل (لبه های خروجی) = 1 و در بهترین حالت حتی اگر همه افراد دیگر به او اعتماد کنند (البته قاضی شهر به او اعتماد نخواهد کرد) بنابراین حداکثر (لبه های ورودی) = n-2
حداکثر اختلاف لبه های ورودی و خروجی برای این شخص n-2- (1) = n-3 است.
همچنین اگر قاضی شهر وجود نداشته باشد ، هیچ کس نمی تواند اختلاف n-1 بین تعداد لبه های ورودی و خروجی را بدست آورد.

اکنون ، وظیفه اصلی ما محاسبه اختلاف یعنی تعداد لبه های ورودی است - تعداد لبه های خروجی برای هر شخص. ما این کار را با رد و بدل کردن آرایه اعتماد انجام خواهیم داد.
در هر ردیف ، دو عنصر وجود دارد. عنصر چپ کسی است که اعتماد می کند و عنصر راست کسی است که عنصر چپ به او اعتماد دارد.
بنابراین عنصر سمت چپ دارای عنصر لبه خروجی به سمت راست است. از این رو ، مقدار اختلاف برای عنصر سمت چپ 1 و برای عنصر راست ، 1 افزایش می یابد.
در کد ما برای این کار از آرایه netTrustGains استفاده کرده ایم. هر شاخص i این آرایه مقدار اختلاف را برای هر شخص نشان می دهد.

پس از عبور از آرایه اعتماد ، a را اجرا خواهیم کرد حلقه برای هر شخص از 1 تا n و بررسی کنید که آیا فردی اختلاف تفاوتی دارد = n-1.
اگر چنین شخصی پیدا شود ، ما او را باز خواهیم گرداند ، ما باز خواهیم گشت -1.

راه حل شهر قاضی Leetcode را پیدا کنید

پیاده سازی

برنامه C ++ برای یافتن راه حل Leetcode برای قاضی شهر

#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 ، اعتماد. اندازه ())): ما حلقه اعتماد را بصورت خطی طی کرده و یک حلقه دیگر به اندازه n برای بررسی netTrustGains برای هر شخص از 1 تا n است.

پیچیدگی فضا 

بر) : ما یک آرایه ایجاد کرده ایم netTrustGains با اندازه n + 1 بنابراین فضای پیچیدگی O (n).