題目連結: https://leetcode.com/problems/top-k-frequent-elements/

參考解法: https://leetcode.com/problems/top-k-frequent-elements/discuss/1653407/Swift-O(N)-using-bucket

練習提問:
Q: nums 可能為empty array嗎?
Q: nums中的element可能為負數嗎？
Q: k可能為0嗎？
Q: frequency會重複嗎？

法ㄧ(Brute force) Time complexity: O(nlogn)

func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
    guard nums.count > 0 else { return [] }
    var dic: [Int: Int] = [:]
    for item in nums {
        dic[item, default: 0] += 1
    }

    let frequencyArray = dic.values.sorted(by: >)

    var result: [Int] = []
    let lowestFrequency = k - 1 < frequencyArray.count ? frequencyArray[k-1] : (frequencyArray.last ?? 0)
    for (key, value) in dic {
        if value >= lowestFrequency {
            result.append(key)
        }
    }
    return result
}

法二(Bucket sort) Time complexity: O(n)

func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
    guard nums.count > 0 || k == 0 else { return [] }
    var dic: [Int: Int] = [:]
    var maxFrequency = 0
    for item in nums {
        dic[item, default: 0] += 1
        if maxFrequency < dic[item, default: 0] {
            maxFrequency = dic[item, default: 0]
        }
    }

    var bucket = Array(repeating: [Int](), count: maxFrequency + 1)

    for (key, value) in dic {
        bucket[value].append(key)
    }

    var result: [Int] = []
    var count = 0
    for i in (0 ..< bucket.count).reversed() {
        if bucket[i].count > 0 {
            result += bucket[i]
            count += bucket[i].count
        }
        if count >= k {
            break
        }
    }
    return result
}