題目連結(jié):
題目意譯:
你被給定一個有著 n 個節(jié)點其編號為 0 到 n - 1 的有向圖,其中每個節(jié)點恰好有一條向外的邊。
該圖以一個索引值從 0 開始且長度 n 的整數(shù)陣列給定,其中 edges[i] 代表著有一條邊從節(jié)點 i 導(dǎo)向至節(jié)點 edges[i]。
節(jié)點 i 的「邊分數(shù)」定義為所有有著一條邊指向 i 的節(jié)點之編號之總和。
回傳有著最高邊分數(shù)的節(jié)點。如果有多個節(jié)點有著相同的邊分數(shù),則回傳索引值最小者。
限制:
n == edges.length
2 ≦ n ≦ 10 ^ 5
0 ≦ edges[i] < n
edges[i] != i
範例測資:
範例 1:
輸入: edges = [1,0,0,0,0,7,7,5]
輸出: 7
解釋:
節(jié)點 1 、 2 、 3 和 4 各有一條邊指向節(jié)點 0。節(jié)點 0 的邊分數(shù)為 1 + 2 + 3 + 4 = 10。
節(jié)點 0 各有一條邊指向節(jié)點 1。節(jié)點 1 的邊分數(shù)為 0。
節(jié)點 7 各有一條邊指向節(jié)點 5。節(jié)點 5 的邊分數(shù)為 7。
節(jié)點 5 和 6 各有一條邊指向節(jié)點 7。節(jié)點 7 的邊分數(shù)為 5 + 6 = 11。
節(jié)點 7 有著最高的邊分數(shù)值,所以回傳 7。
範例 2:
輸入: edges = [2,0,0,2]
輸出: 0
解釋:
節(jié)點 1 和 2 各有一條邊指向節(jié)點 0。節(jié)點 0 的邊分數(shù)為 1 + 2 = 3。
節(jié)點 0 和 3 各有一條邊指向節(jié)點 2。節(jié)點 2 的邊分數(shù)為 0 + 3 = 3。
節(jié)點 0 和 2 都有著邊分數(shù)值 3。由於節(jié)點 0 的索引值較小,我們回傳 0。
解題思維:
就掃過一次 edges,然後看哪些節(jié)點出現(xiàn)最多次即可(方式很多:可以直接統(tǒng)計再看哪個編號最多;也可以排序後,使得相同編號聚在一起,然後再統(tǒng)計)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。