ค้นหา Town Judge Leetcode Solution


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน
กราฟ

คำชี้แจงปัญหา

ในปัญหานี้เราได้รับ n คนที่ติดป้ายกำกับจาก 1 ถึง n เรายังได้รับ 2d แถว ความไว้วางใจ [] [] แสดงให้เห็นว่าคนที่เชื่อใจ [i] [0] คนนั้นไว้วางใจ [i] [1] คนที่มีต่อคนอื่น ๆ
เราต้องหาคนที่เป็น "ผู้พิพากษาเมือง" ที่ไม่ไว้วางใจคนอื่นและคนอื่น ๆ ทั้งหมดก็เชื่อใจเขา หากไม่มีบุคคลดังกล่าวให้กลับ -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 สำหรับผู้ตัดสินเมืองเท่านั้น
ถ้าเราพูดถึงคนง่ายๆเขาก็จะเชื่อใจผู้พิพากษาของเมืองอย่างแน่นอนดังนั้น min (ขอบขาออก) = 1 และในกรณีที่ดีที่สุดแม้ว่าคนอื่น ๆ ทั้งหมดจะเชื่อใจเขา (แน่นอนว่าผู้พิพากษาของเมืองจะไม่เชื่อใจเขา) ดังนั้น max (ขาเข้า) = n-2
ความแตกต่างสูงสุดระหว่างขอบขาเข้าและขาออกสำหรับบุคคลนี้คือ n-2- (1) = n-3
นอกจากนี้หากไม่มีผู้พิพากษาประจำเมืองก็จะไม่มีใครสามารถบรรลุความแตกต่าง n-1 ระหว่างจำนวนขอบขาเข้าและขาออก

ตอนนี้งานหลักของเราคือการคำนวณความแตกต่างเช่นจำนวนขอบขาเข้า - จำนวนขอบขาออกสำหรับแต่ละคน เราจะทำได้โดยการข้ามผ่านแถวอาร์เรย์ที่เชื่อถือได้
ในแถวใดก็ได้มีสององค์ประกอบ องค์ประกอบด้านซ้ายคือผู้ที่ไว้วางใจและองค์ประกอบด้านขวาคือผู้ที่องค์ประกอบด้านซ้ายไว้วางใจ
ดังนั้นองค์ประกอบด้านซ้ายจึงมีขอบขาออกไปยังองค์ประกอบด้านขวา ดังนั้นค่าความแตกต่างขององค์ประกอบด้านซ้ายจะลดลง 1 และสำหรับองค์ประกอบด้านขวาจะเพิ่มขึ้น 1
ในโค้ดของเราเราได้ใช้อาร์เรย์ netTrustGains สำหรับงานนี้ ดัชนี i แต่ละตัวของอาร์เรย์นี้แสดงค่าความแตกต่างของแต่ละบุคคล

หลังจากสำรวจอาร์เรย์ที่เชื่อถือได้เราจะเรียกใช้ไฟล์ ห่วง สำหรับแต่ละคนตั้งแต่ 1 ถึง n และตรวจสอบว่าบุคคลใดมีค่าความแตกต่าง = n-1
หากพบบุคคลดังกล่าวเราจะส่งคืนให้เขาอีกครั้งเราจะส่งคืน -1

ค้นหา Town Judge Leetcode Solution

การดำเนินงาน

โปรแกรม 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 สำหรับ Find the Town Judge Leetcode Solution

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, trust.size ())): เราได้สำรวจลูปความไว้วางใจแบบเชิงเส้นและอีกวงหนึ่งมีขนาด n เพื่อตรวจสอบ netTrustGains สำหรับแต่ละคนตั้งแต่ 1 ถึง n

ความซับซ้อนของอวกาศ 

บน) : เราได้สร้างอาร์เรย์ netTrustGains ขนาด n + 1 ดังนั้นความซับซ้อนของพื้นที่ O (n)