Знайдзіце рашэнне гарадскога суддзі Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка
Графік

Пастаноўка праблемы

У гэтай праблеме нам дадзена n людзей, пазначаных ад 1 да n. Нам таксама даюць 2d масіў давер [] [] паказвае, што давер [i] [0] -ы чалавек давярае даверу [i] [1] -му чалавеку для кожнага 0 <= i <trust.length.
Мы павінны знайсці чалавека "гарадскога суддзю", які не давярае іншым людзям, і ўсе іншыя людзі давяраюць яму. Калі такога чалавека не існуе, вярніце -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 толькі для гарадскога суддзі.
Калі казаць пра простага чалавека, то ён напэўна будзе давяраць гарадскому суддзі, такім чынам, min (выходныя краю) = 1, а ў лепшым выпадку, нават калі ўсе астатнія яму давяраюць (вядома, гарадскі суддзя яму не давярае), такім чынам, max (уваходныя краю) = п-2.
Максімальная розніца паміж уваходнымі і выходнымі краямі для гэтага чалавека складае n-2- (1) = n-3.
Акрамя таго, калі няма гарадскога суддзі, ніхто не можа дасягнуць розніцы n-1 паміж колькасцю ўваходных і выходных краёў.

Цяпер наша асноўная задача - вылічыць розніцу, гэта значыць колькасць уваходных краёў - колькасць выходных краёў для кожнага чалавека. Мы зробім гэта, абыходзячы масіў даверу па шэрагу.
У любым шэрагу ёсць два элементы. Левы элемент - гэта хто давярае, а правы - каму давярае левы элемент.
Такім чынам левы элемент мае выходны край да правага элемента. Такім чынам, значэнне розніцы для левага элемента зменшыцца на 1, а для правага элемента - на 1.
У нашым кодзе для гэтай задачы мы выкарысталі масіў netTrustGains. Кожны індэкс i гэтага масіва паказвае значэнне розніцы для i-га чалавека.

Пасля праходжання масіва даверу мы запусцім пятля для кожнага чалавека ад 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

Праграма Java для пошуку рашэнне гарадскога суддзі Leetcode

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 (макс (п, давер.памер ())): Мы абышлі цыкл даверу лінейна, і іншы цыкл мае памер n, каб праверыць netTrustGains для кожнага чалавека ад 1 да n.

Касмічная складанасць 

O (n): Мы стварылі масіў netTrustGains памерам n + 1, такім чынам, складанасць прасторы O (n).