題目敘述
題目會給定我們一個比賽紀錄陣列matches，裡面以pair的方式儲存，每個pair的第一個欄位代表這場比賽的贏家ID，第二個欄位代表這場比賽的輸家ID。
題目要求我們找出所有沒有輸的玩家ID，和只輸一場的玩家ID。
計算時，只考慮有比賽紀錄的玩家。輸出時，依照遊戲玩家的ID，從小到大做排列。
測試範例
Example 1:
Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].
Example 2:
Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] = [1,2,5,6] and answer[1] = [].
約束條件
Constraints:
1 <= matches.length <= 10^5
比賽陣列的長度介於1 ~ 10^5之間。
matches[i].length == 2
每條比賽紀錄都是一組pair。
1 <= winneri, loseri<= 10^5
贏家ID和輸家ID都介於1 ~ 10^5 之間。
winneri!= loseri
同一場比賽，贏家ID 一定不等於 輸家ID
- All
matches[i]are unique.
所有的比賽紀錄都是獨一無二的，不會重複。
演算法
這題的關鍵在於統計"輸"的次數。
第一個是計算沒有輸，相當於輸的場次是0次。
為了避免和沒有出賽紀錄混淆，我們稍後在程式碼會特別標記為-1，作為有比賽而且沒有輸過的區別。
第二個是計算只輸一場，相當於輸的計數器的值為1。
最後，建造一個迴圈檢查，依照題意，輸出沒有輸和只輸一場的玩家ID，並且依照ID大小，從小到大排列即可。
程式碼
class Solution:
def findWinners(self, matches):
losses = defaultdict(int)
for winner, loser in matches:
# For winner
if losses[winner] == 0:
losses[winner] = -1
# For loser
if losses[loser] == -1:
losses[loser] = 1
else:
losses[loser] += 1
zero_loss = [i for i in range(1, 100001) if losses[i] == -1]
one_loss = [i for i in range(1, 100001) if losses[i] == 1]
return [zero_loss, one_loss]
複雜度分析
時間複雜度:
從頭到尾掃描過每個場比賽紀錄，所需時間為O(n)
空間複雜度:
需要額外一個字典去紀錄輸的次數，最大為O(n)
關鍵知識點
看到需要統計次數，聯想到雜湊映射表 Hash table，
在Python的實現就是字典dictionary。
Reference:
