每日一題
日期
2025/9/18
前置
LeetCode 有引入 swift-collections 1.1.4 ，這篇就會用其中的 Heap 資料結構而不自己實作。
經過多次改善、簡化後最快有到 118ms
想法與資料結構
swift-collections 提供的 Heap 無法有效率地移除，像是需要使用 unordered 陣列、找到目標物、最後再重新生成 Heap 。時間複雜度和空間複雜度都可觀之外，寫出來的程式碼也變得複雜難讀。
於是根據題意： taskId 是唯一，這篇的資料結構就可以這樣應用：
- HashMap: 維持 taskId: task pairs，可以幫助我們快速以 taskId 取得 task 。 (O(1))
- Heap: 維持排序，無論是刪或加， task 都只進不出。當要進行
execTop()過程，只要 pop 到過時的 task 時直接忽略即可。
class TaskManager {
// 用來 Heap 排序的容器，其中的元素只增不減。在 pop 時和 taskMap 對照當下 task 的合法性
private var tasks = Heap<Task>()
// 識別現有 Task 的 Map, [taskId: Task]
private var taskMap = [Int: Task]()
/* To be continue */
}
Task 構造
根據題意，
priority相同時，taskId較大者為大
struct Task: Comparable {
let userId: Int
let taskId: Int
let priority: Int
// MARK: Comparable
static func < (lhs: Task, rhs: Task) -> Bool {
guard lhs.priority != rhs.priority else {
return lhs.taskId < rhs.taskId
}
return lhs.priority < rhs.priority
}
}
新增的核心邏輯
init 裡面、edit 都會用到生成 Task ，插入 Heap, HashMap 的邏輯就集中到這裡
class TaskManager {
/* 省略 */
/// 生成 Task 並插入 HashMap 和 Heap
func add(_ userId: Int, _ taskId: Int, _ priority: Int) {
let task = Task(
userId: userId,
taskId: taskId,
priority: priority
)
tasks.insert(task)
taskMap[task.taskId] = task
}
/* 省略 */
}
初始化
走訪完美一個子陣列，直接呼叫 add 即可
class TaskManager {
/* 省略 */
init(_ tasks: [[Int]]) {
for task in tasks {
add(task[0], task[1], task[2])
}
}
/* 省略 */
}
編輯
在編輯的時候，依據前面提到的處理方式， Heap 裡的 task 只出不進。這邊找到對應的 task 、取用 userId 後新增一個新的 task 。
class TaskManager {
/* 省略 */
func edit(_ taskId: Int, _ newPriority: Int) {
guard let task = taskMap[taskId] else { return }
add(task.userId, taskId, newPriority)
}
/* 省略 */
}
移除
因為 Heap 裡的 task 只出不進，這邊就只需要把 HashMap 裡面 key 為 taskId 的值清除就好了
class TaskManager {
/* 省略 */
func rmv(_ taskId: Int) {
taskMap[taskId] = nil
}
/* 省略 */
}
回傳最大 task 的 userId
因為 Heap 裡的 task 只出不進，所以我們這邊有兩個步驟
- 呼叫 popMax 彈出一個 task
- 彈出的 task 有在 HashMap 裡，否則忽略， 繼續 1. 彈出下一個最大值
class TaskManager {
/* 省略 */
func execTop() -> Int {
while let top = tasks.popMax() { // 1.
if taskMap[top.taskId] == top { // 2.
taskMap[top.taskId] = nil
return top.userId
}
}
return -1
}
/* 省略 */
}
最終程式碼
class TaskManager {
/// 用來 Heap 排序的容器，其中的元素只增不減
private var tasks = Heap<Task>()
/// 識別現有 Task 的 Map, [taskId: Task]
private var taskMap = [Int: Task]()
init(_ tasks: [[Int]]) {
for task in tasks {
add(task[0], task[1], task[2])
}
}
/// 生成 Task 並插入 HashMap 和 Heap
func add(_ userId: Int, _ taskId: Int, _ priority: Int) {
let task = Task(
userId: userId,
taskId: taskId,
priority: priority
)
tasks.insert(task)
taskMap[task.taskId] = task
}
func edit(_ taskId: Int, _ newPriority: Int) {
guard let task = taskMap[taskId] else { return }
add(task.userId, taskId, newPriority)
}
/// 只移除 HashMap 裡面的元素
func rmv(_ taskId: Int) {
taskMap[taskId] = nil
}
func execTop() -> Int {
while let top = tasks.popMax() {
if taskMap[top.taskId] == top {
taskMap[top.taskId] = nil
return top.userId
}
}
return -1
}
}
struct Task: Comparable {
let userId: Int
let taskId: Int
let priority: Int
// MARK: Comparable
static func < (lhs: Task, rhs: Task) -> Bool {
guard lhs.priority != rhs.priority else {
return lhs.taskId < rhs.taskId
}
return lhs.priority < rhs.priority
}
}
