前往
大廳
主題

LeetCode - 2225. Find Players With Zero or One Losses 解題心得

Not In My Back Yard | 2022-12-12 12:00:10 | 巴幣 100 | 人氣 163

題目連結:


題目意譯:
你被給定一整數陣列 matches,其中 matches[i] = [winneri, loseri] 代表著在一場競賽中選手 winneri 打敗了選手 loseri。

回傳一大小為 2 的列表 answer,其中:
answer[0] 為所有沒有輸過任何一場競賽的選手所形成的一個列表。
answer[1] 為所有恰好只輸過一場競賽的選手所形成的一個列表。

兩個列表中的數值應按照升序順序排列。

注:
你只應考慮那些至少有比過一場競賽的選手們。
測試資料之生成滿足不會有兩次競賽有著一模一樣的結果。

限制:
1 ≦ matches.length ≦ 10 ^ 5
matches[i].length == 2
1 ≦ winneri, loseri ≦ 10 ^ 5
winneri != loseri
matches[i] 彼此相異。



範例測資:
範例 1:
輸入: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
輸出: [[1,2,10],[4,5,7,8]]
解釋:
選手 1 、 2 和 10 都沒有輸過任何一場競賽。
選手 4 、 5 、 7 和 8 各自輸過一次競賽。
選手 3 、 6 和 9 各自輸過兩次競賽。
因此 answer[0] = [1,2,10] 而 answer[1] = [4,5,7,8]。

範例 2:
輸入: matches = [[2,3],[1,3],[5,4],[6,4]]
輸出: [[1,2,5,6],[]]
解釋:
選手 1 、 2 、 5 和 6 都沒有輸過任何一場競賽。
選手 3 和 4 各自輸過一兩次競賽。
因此 answer[0] = [1,2,5,6] 而 answer[1] = []。


解題思維:
因為選手的編號最大也才 100000,所以我們可以直接用兩個陣列來儲存每位選手有沒有比過賽,以及各自輸過多少次(如果編號範圍更大的話,則需要改用雜湊表(Hash Table)來儲存哪些選手編號有出現過,然後各自輸了多少次)。

最後直接掃過所有可能的選手編號(即 1 ~ 100000),看哪些人有比過賽。然後這些比過賽的人,如果一次都沒輸就把該編號放到 answer[0] 中;而如果只輸過一次則放到 answer[1] 中。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作