leetcode解題：(Medium) 2225. Find Players With Zero or One Losses

題目：https://leetcode.com/problems/find-players-with-zero-or-one-losses/description/

描述：輸入許多比賽勝負結果的資料，分別找出完全沒輸過以及正好輸一場的選手們的編號，輸出結果的編號需要遞增排序好

解題思路：要找出現頻率就是map出場的時間，用HashMap紀錄所有出場選手的敗場次數，再將次數為0跟1的資料找出並排序後輸出即可

程式碼：(HashMap)

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Map<Integer, Integer> lostCount = new HashMap<>();

        for(int[] match : matches) {
            if(!lostCount.containsKey(match[0])) lostCount.put(match[0], 0);
            if(lostCount.containsKey(match[1])) lostCount.put(match[1], lostCount.get(match[1])+1);
            else lostCount.put(match[1], 1);
        }

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> noLost = new ArrayList<>();
        List<Integer> oneLost = new ArrayList<>();

        for(int key : lostCount.keySet()) {
            if(lostCount.get(key) == 0) noLost.add(key);
            if(lostCount.get(key) == 1) oneLost.add(key);
        }

        Collections.sort(noLost);
        Collections.sort(oneLost);

        result.add(noLost);
        result.add(oneLost);

        return result;
    }
}

---

或是也可以採用輸入時會自動排序的TreeMap，這樣在找尋輸出的資料後就不需在進行一次排列，雖然沒有比較快(leetcode中實際用時比用HashMap還慢)，不過因為我之前沒用過且TreeMap本身的特性(自動排序的map&底層使用紅黑樹)很實用，以後肯定還有要用到的機會所以先記錄一下

程式碼：(TreeMap)

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Map<Integer, Integer> lostCount = new TreeMap<>();

        for(int[] match : matches) {
            if(!lostCount.containsKey(match[0])) lostCount.put(match[0], 0);
            if(lostCount.containsKey(match[1])) lostCount.put(match[1], lostCount.get(match[1])+1);
            else lostCount.put(match[1], 1);
        }

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> noLost = new ArrayList<>();
        List<Integer> oneLost = new ArrayList<>();

        for(int key : lostCount.keySet()) {
            if(lostCount.get(key) == 0) noLost.add(key);
            if(lostCount.get(key) == 1) oneLost.add(key);
        }

        result.add(noLost);
        result.add(oneLost);

        return result;
    }
}

時間複雜度：O(nlogn)
空間複雜度：O(n)

tags: leetcode medium map/set red-black tree