技术凡人

Appearance

997-找到小镇的法官 ​

这个题目是一个简单的题目，我自己的思路是建立一个投票机制，自己投票给别人就会让自己少一票，并且被投票的人票数就是加一。最后看能不能找到票数等于n-1的那个人，找到就是法官，找不到就是没有法官。

代码如下

java
class Solution {
    public int findJudge(int n, int[][] trust) {
        Set<Integer> intset = new HashSet<>();
        /*用一个数组表示投票*/
        int[] arr = new int[n];
        for(int i = 0 ;i< trust.length;i++){
            /** 信任别人表示自己不是法官 */
            arr[trust[i][0]-1]--;
            /** 给信任的人投票 */
            arr[trust[i][1]-1]++;
        }
        for(int i = 0 ;i< arr.length;i++){
            /** 票数等于n-1的人就是法官本人了 */
            if(arr[i]== (n-1)){
                return i +1;
            }
        }
        /** 到最后一步没找到法官 */
        return -1;
    }
}
class Solution {
    public int findJudge(int n, int[][] trust) {
        Set<Integer> intset = new HashSet<>();
        /*用一个数组表示投票*/
        int[] arr = new int[n];
        for(int i = 0 ;i< trust.length;i++){
            /** 信任别人表示自己不是法官 */
            arr[trust[i][0]-1]--;
            /** 给信任的人投票 */
            arr[trust[i][1]-1]++;
        }
        for(int i = 0 ;i< arr.length;i++){
            /** 票数等于n-1的人就是法官本人了 */
            if(arr[i]== (n-1)){
                return i +1;
            }
        }
        /** 到最后一步没找到法官 */
        return -1;
    }
}

官方题解 ​

官方的题解使用入度和出度的概念，这是数据结构上的概念，这个很好理解就是被别的节点指向就是入度，指向别人的点就是出度，最后找到入度是n-1的那个人并且出度是0就是法官。