題目連結: 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
}