欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C/C++哈希表優(yōu)化LeetCode題解997找到小鎮(zhèn)的法官

 更新時(shí)間:2022年12月28日 10:35:20   作者:彤哥來刷題啦  
這篇文章主要為大家介紹了C/C++哈希表優(yōu)化題解997找到小鎮(zhèn)的法官示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

方法一、哈希表

今天這道題比較簡單,我們可以統(tǒng)計(jì)每個(gè)人信任別人的數(shù)量和被信任的數(shù)量,如果存在某個(gè)人信任別人的數(shù)量為0,且被信任的數(shù)量為 n-1,那么,這個(gè)人就是法官。

因?yàn)楸绢}的數(shù)據(jù)范圍為 [1,1000],數(shù)據(jù)范圍比較小,所以,直接使用數(shù)組作為哈希表來使用。

請看代碼:

class Solution {
    public int findJudge(int n, int[][] trust) {
        // 不信任任何人的人 & 被所有人信任的人
        // 計(jì)算每個(gè)人信任的人的數(shù)量和被信任的數(shù)量
        // 前者等于0,后者等于n-1
        int[][] arr = new int[n + 1][2];
        for (int[] t : trust) {
            // 0表示信任別人
            arr[t[0]][0]++;
            // 1表示被別人信任
            arr[t[1]][1]++;
        }
        
        for (int i = 1; i <= n; i++) {
            if (arr[i][0] == 0 && arr[i][1] == n - 1) {
                return i;
            }
        }
                return -1;
    }
}
  • 時(shí)間復(fù)雜度:O(m),m 為 trust 數(shù)組的長度。
  • 空間復(fù)雜度:O(n)。

運(yùn)行結(jié)果如下:

方法二、優(yōu)化

方法一中,我們使用了一個(gè)二維數(shù)組的第二維表示信任別人的數(shù)量和被別人信任的數(shù)量,其實(shí),我們也可以使用一個(gè)一維數(shù)組來求解, 減一表示信任別人的數(shù)量,加一表示被別人信任的數(shù)量,那么,只有法官才可能達(dá)到 n-1 的總數(shù)量。

請看代碼:

class Solution {
    public int findJudge(int n, int[][] trust) {
        // 不信任任何人的人 & 被所有人信任的人
        int[] arr = new int[n + 1];
        for (int[] t : trust) {
            // 減一表示信任別人
            arr[t[0]]--;
            // 加一表示被別人信任
            arr[t[1]]++;
        }
        
        for (int i = 1; i <= n; i++) {
            // 因?yàn)楸粍e人信任不可能超過 n-1
            // 所以,只有法官能達(dá)到 n-1
            // 且法官信任別人數(shù)量為 0
            // 所以,總的數(shù)量為 n-1
            if (arr[i] == n - 1) {
                return i;
            }
        }
                return -1;
    }
}
  • 時(shí)間復(fù)雜度:O(m),m 為 trust 數(shù)組的長度。
  • 空間復(fù)雜度:O(n)。

以上就是C/C++哈希表優(yōu)化LeetCode題解997找到小鎮(zhèn)的法官的詳細(xì)內(nèi)容,更多關(guān)于C/C++哈希表優(yōu)化找到小鎮(zhèn)法官的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C++中的數(shù)組你真的理解了嗎

    C++中的數(shù)組你真的理解了嗎

    這篇文章主要為大家詳細(xì)介紹了C++的數(shù)組,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-02-02
  • C語言解決堆棧括號匹配問題示例詳解

    C語言解決堆棧括號匹配問題示例詳解

    這篇文章主要為大家介紹了C語言堆棧括號匹配問題示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2021-11-11
  • 用C語言實(shí)現(xiàn)掃雷游戲

    用C語言實(shí)現(xiàn)掃雷游戲

    這篇文章主要為大家詳細(xì)介紹了用C語言實(shí)現(xiàn)掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-06-06
  • C++實(shí)現(xiàn)動態(tài)順序表

    C++實(shí)現(xiàn)動態(tài)順序表

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)動態(tài)順序表,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-05-05
  • C語言編程內(nèi)存分配通訊錄靜態(tài)實(shí)現(xiàn)示例代碼教程

    C語言編程內(nèi)存分配通訊錄靜態(tài)實(shí)現(xiàn)示例代碼教程

    這篇文章主要為大家介紹了C語言編程實(shí)現(xiàn)靜態(tài)的通訊錄示例代碼教程,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2021-10-10
  • C++詳細(xì)講解print緩沖區(qū)的刷新

    C++詳細(xì)講解print緩沖區(qū)的刷新

    這篇文章主要介紹了print緩沖區(qū)刷新問題,實(shí)現(xiàn)代碼簡單易懂,具有很好的參考價(jià)值,希望對大家有所幫助,需要的朋友可以參考下
    2022-05-05
  • c++輸出斐波那契數(shù)列示例分享

    c++輸出斐波那契數(shù)列示例分享

    這篇文章主要介紹了c++輸出斐波那契數(shù)列示例,需要的朋友可以參考下
    2014-03-03
  • C語言實(shí)現(xiàn)獲取文件MD5值

    C語言實(shí)現(xiàn)獲取文件MD5值

    MD5(Message?Digest?Algorithm?5)是一種常用的哈希函數(shù)算法,這篇文章主要介紹了C語言如何獲取文件MD5值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2023-08-08
  • C++STL函數(shù)和排序算法的快排以及歸并排序詳解

    C++STL函數(shù)和排序算法的快排以及歸并排序詳解

    這篇文章主要為大家詳細(xì)介紹了C++STL函數(shù)和排序算法的快排以及歸并排序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03
  • C++STL之vector模板類詳解

    C++STL之vector模板類詳解

    這篇文章主要為大家詳細(xì)介紹了C++vector模板類,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03

最新評論