מצא את הפתרון של שופט העיר 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 מראה ש- אמון על b.
שופט עירוני אינו סומך על אף אחד כך, לשופט העיר אין שום יתרון יוצא. כל שאר אנשי ה- N-1 סומכים כך על שופט העיר, סך הכל הקצה הנכנס n-1 כלפי שופט העיר מכל האדם האחר.
אנו יכולים להבין עוד כי ההבדל בין מספר הקצוות הנכנסים למספר הקצוות היוצאים הוא n-1 עבור שופט העיר בלבד.
אם נדבר על אדם פשוט אז הוא בוודאי יסמוך על שופט העיר כך שמיני (קצוות יוצאים) = 1 ובמקרה הטוב גם אם כל האחרים סומכים עליו (כמובן ששופט העיר לא יסמוך עליו) ובכך מקסימום (קצוות נכנסים) = n-2.
ההבדל המרבי בין קצוות נכנסים ויוצאים עבור אדם זה הוא n-2- (1) = n-3.
כמו כן, אם אין שופט עירוני, איש אינו יכול להשיג את ההבדל n-1 בין מספר הקצוות הנכנסים והיוצאים.

כעת, המשימה העיקרית שלנו היא לחשב את ההפרש כלומר מספר הקצוות הנכנסים - מספר הקצוות היוצאים לכל אדם. אנו נעשה זאת על ידי מעבר במערך האמון בשורה.
בכל שורה יש שני אלמנטים. אלמנט שמאלי הוא מי שסומך עליו ואלמנט ימני הוא על מי יסוד שמאל.
לפיכך לאלמנט השמאלי יש אלמנט קצה לימין. לפיכך, ערך ההפרש עבור האלמנט השמאלי יקטן ב -1 ואלמנט הימני, יגדל ב -1.
בקוד שלנו השתמשנו במערך netTrustGains למשימה זו. כל אינדקס i של מערך זה מציג את ערך ההפרש לאדם זה.

לאחר חציית מערך האמון, נפעיל א לולאה עבור כל אדם מ -1 עד n ובדוק אם לאדם כלשהו יש ערך ההפרש = n-1.
אם יימצא אדם כזה אז נחזיר אותו אחרת נחזור -1.

מצא את הפתרון של שופט העיר 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

תוכנית 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

ניתוח מורכבות למציאת פתרון שופט העיר שופט

מורכבות זמן

O (מקסימום (n, trust.size ())): עברנו את לולאת האמון בצורה לינארית ולולאה אחרת היא בגודל n כדי לבדוק את netTrustGains עבור כל אדם מ -1 עד n.

מורכבות בחלל 

O (n): יצרנו מערך netTrustGains בגודל n + 1 ובכך מורכבות שטח O (n).