LeetCode – 347. Top K Frequent Elements

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
}``````