347. Top K Frequent Elements

題目

• https://leetcode.com/problems/top-k-frequent-elements/

思路

使用兩個 dictionary 來追蹤出現次數

• 第一個： key 為數字, value 為 count
• 第二個： key 為 count, value 為存有數字的 set

另外紀錄目前技術的最大值，在第二段處理時遞減取用第二的 dictionary

處理分成兩段：

記錄次數

走訪所有的元素。走訪的過程更新記數的 dictionary ，並更新

組合 result array

從 max 開始取用第二個 array ，直到滿足 k 個數字為止。

程式碼

class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        guard !nums.isEmpty else { return [] }

        var most = 0
        var map = [Int: Int]()
        var reverse = [Int: Set<Int>]()
        
        for num in nums {
            var count = map[num] ?? 0
            reverse[count]?.remove(num)
            count += 1
            map[num] = count
            reverse[count, default: Set<Int>()].insert(num)
            most = max(most, count)
        }
        
        var remaining = k
        var result = [Int]()
        var current = most
        
        while remaining > 0 && current >= 0 {
            if let set = reverse[current] {
                remaining -= set.count
                result.append(contentsOf: Array(set))
                current -= 1
            }
        }
        
        return result
    }
}

後記

直覺自己在資料操作上雖然可以快速取得最大次數的數字，但是過程覺得有點複雜

雖然照著第一想法寫出來有辦法 AC

接著來看看官方解法，看有什麼比較好的寫法