🔗 🟡 2225. Find Players With Zero or One Losses 1316

tags: `Weekly Contest 287` `雜湊表(Hash Table)` `排序(Sorting)`

題意

給定一個整數陣列 $matches$ 其中 $matches[i] = [winner_i, loser_i]$ 表示在比賽中球員 $winner_i$ 打敗了球員 $loser_i$ 。

返回一個長度為 $2$ 的列表 $answer$ ：

$answer[0]$ 是所有沒有輸掉任何比賽的球員列表。
$answer[1]$ 是所有恰好輸掉一場比賽的球員列表。

只需考慮參加過 至少一場 比賽的球員，且答案中的值都需按遞增順序返回。

思路：雜湊表(Hash Table) + 排序(Sorting)

使用一個雜湊表 $cnt$ 來記錄每個球員的 輸掉比賽次數，然後對 $cnt$ 的 key 進行排序，將 $cnt[k] = 0$ 的球員加入到 $answer[0]$ 中，將 $cnt[k] = 1$ 的球員加入到 $answer[1]$ 中。

但需要注意，由於我們在添加到 $cnt$ 時，只對 $loser_i$ 進行 $cnt$ 的增加，但考慮答案時也需要考慮到沒輸過的球員，因此可以另外維護一個 Hash Set $players$ ，或是在 $winner_i$ 第一次出現時將其也添加到 $cnt$ 中，並且初始化為 $0$ 。

此外，由於我們只在意答案中的球員順序，因此也可以先添加到答案後，再對答案進行排序，這樣應該會略快一些。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ ，主要是排序的時間複雜度。
空間複雜度： $\mathcal{O}(n)$ ，使用雜湊表來記錄每個球員的輸掉比賽次數，而最多會有 $2n$ 個球員。

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        cnt = defaultdict(int)
        for x, y in matches: # x is winner, y is loser
            cnt[x] = cnt[x] # insert key if not exist
            cnt[y] += 1
        ans = [[], []]
        for p in sorted(cnt.keys()): # 這裡是先排序，但先添加到答案後，再對答案進行排序應該會略快一些
            if cnt[p] == 0:
                ans[0].append(p)
            elif cnt[p] == 1:
                ans[1].append(p)
        return ans

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) {
        vector<vector<int>> ans(2);
        unordered_map<int, int> cnt; // 用 map 就不用排序，但會略慢一些
        for (auto& match : matches) {
            int x = match[0], y = match[1];
            if (!cnt.count(x)) cnt[x] = 0; // 插入 key
            cnt[y]++;
        }
        for (auto kv : cnt) {
            int k = kv.first, v = kv.second;
            if (cnt[k] == 0) ans[0].push_back(k);
            else if (cnt[k] == 1) ans[1].push_back(k);
        }
        sort(ans[0].begin(), ans[0].end());
        sort(ans[1].begin(), ans[1].end());
        return ans;
    }
};