找出沒有輸和只輸一次的玩家 Leetcode #2225

JESHOOTS.COM null on Unsplash

題目敘述

題目會給定我們一個比賽紀錄陣列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:

[1] Python by counting and dictionary [w/ Comment]