Leetcode 2225 - Find Players With Zero or One Losses

題目

Problem#

給你一個陣列 match[i] = (winner_i, loser_i) 代表winner_i 在第 i 場比賽贏了 loser_i，要你回傳沒有輸過的人、和只輸一場的人有哪些（回傳要遞增排序）。

測資限制#

• $1 \le n \le 10^5$
• $1 \le \text{winner}_i, \text{loser}_i \le 10^5$

想法#

統計贏家與輸家各自的場數，可以用 map/unordered_map ，去所有贏家中找看誰沒出現在輸家中過（沒有輸過），則加到贏家答案中；找輸家中只輸一場的人，加到輸家答案中。

AC Code#

Copy

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches)
    {
        vector<vector<int>> ans(2);
        int n = matches.size();
        unordered_map<int, int> wm, lm;
 
        for(auto i  : matches)
        {
            auto [w, l] = tie(i[0], i[1]);
            wm[w]++;
            lm[l]++;
        }
 
        for(auto [i, cnt] : wm)
        {
            if(!lm.count(i))
                ans[0].push_back(i);
        }
        for(auto [i, cnt] : lm)
        {
            if(cnt == 1)
                ans[1].push_back(i);
        }
        for(int i = 0; i < 2; i++)
            sort(ans[i].begin(), ans[i].end());
        return ans;
    }
};

view raw leetcode/2225.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n\log{n})$
• 空間複雜度: $\mathcal{O}(n)$

心得#

應該是 Easy