C/C++哈希表優(yōu)化LeetCode題解997找到小鎮(zhè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語言編程內(nèi)存分配通訊錄靜態(tài)實(shí)現(xiàn)示例代碼教程
這篇文章主要為大家介紹了C語言編程實(shí)現(xiàn)靜態(tài)的通訊錄示例代碼教程,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2021-10-10