Шаар сотунун Leetcode чечимин табыңыз


Кыйынчылык деңгээли жеңил
Көп суралган Amazon
график

Маселени билдирүү

Бул көйгөйдө бизге 1ден nге чейин n белгиси коюлган. Ошондой эле бизге 2d өлчөмү берилет согуштук тизме ишеним [] [] көрсөткөндөй, ишеним [i] [0] адамдар ар бир 1 <= i <trust.length үчүн ишеним [i] [0] -деген адамдарга ишенишет.
Башка адамдарга ишенбеген жана бардык адамдар ага ишенген адамды "шаар казысы" деп табышыбыз керек. Эгер андай адам жок болсо, анда шаардык сотту кайтарып бериңиз.

мисал

#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 айырмачылыгына жетише албайт.

Эми, биздин негизги милдетибиз - айырманы эсептөө, башкача айтканда ар бир адам үчүн келген кырлардын саны - чыккан кырлардын саны. Биз муну ишенимдүү массивди катарынан өтүү менен жасайбыз.
Кайсы катарда болбосун, эки элемент бар. Сол элемент - ким ишенсе, оң элемент - ким ишенет.
Ошентип, сол элементтин оң жагына чыгуучу чети болот. Демек, сол элемент үчүн айырма мааниси 1ге, ал эми оң элемент үчүн 1ге көбөйөт.
Бул тапшырманы аткаруу үчүн биз кодубузда netTrustGains массивин колдондук. Бул массивдин ар бир индекси ith адам үчүн айырмачылык маанисин көрсөтөт.

Ишеним массивинен өткөндөн кийин, а луп 1ден nге чейинки ар бир адам үчүн жана кандайдыр бир адамдын айырмачылык мааниси бар экендигин текшериңиз = n-1.
Эгер ошондой адам табылса, анда биз аны кайтарып беребиз -1.

Шаар сотунун Leetcode чечимин табыңыз

ишке ашыруу

Шаардык соттун Leetcode чечимин табуу үчүн 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

Шаардык соттун Leetcode чечимин табуу үчүн Java программасы

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

Шаар сотунун Leetcode чечимин табуу үчүн татаалдыкты талдоо

Убакыт татаалдыгы

O (max (n, trust.size ())): Биз ишеним циклин сызыктуу басып өттүк жана дагы бир цикл 1ден nге чейин ар бир адам үчүн netTrustGains текшерүү үчүн n өлчөмүндө.

Космостун татаалдыгы 

O (n): N + 1 өлчөмүндөгү netTrustGains массивин түздүк, ошондуктан O (n) мейкиндигинин татаалдыгы.