😶🌫️
448. Find All Numbers Disappeared in an Array
題目
解法 1 - Hash Set
看完題目後第一個想到的解法
- 宣告一個 set 列出 1 到 n
- 走訪 array
nums
,移除有出現過的數字 - 轉換成 array 回傳
程式碼
class Solution {
func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
guard !nums.isEmpty else { return [] }
var set = Set(1...nums.count)
for num in nums {
set.remove(num)
}
return Array(set)
}
}
缺點
- 宣告 set 和最後需要轉換成 array 會消耗比較多計算資源
- remove 在 leetcode 上比較昂貴
解法 2 - 標記出現過的位置
官方解雖然說這是 in place 解,但是在 Swift 還是要先重新宣告成 var 變數才能開始操作。
第一步,標記
從題目需要檢查 1 到 nums.count 為止哪個數字沒出現,因此就可以利用 array index 來標記。
由於題意是 1 indexed ,所以在標記的時候要針對 -1
的位置不然會超出範圍。
例如走訪 nums[0] 的時候遇到 1 ,就把 nums[(1-1)]
轉換成負值。
第二步,尋找沒被標記的位置
接著再走訪一次 array ,如果值大於零,該 index +1
後就是沒出現過的數值。
程式碼
class Solution {
func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
guard !nums.isEmpty else { return [] }
var nums = nums
for num in nums {
let index = abs(num) - 1
if nums[index] > 0 {
nums[index] *= -1
}
}
var results = [Int]()
var index = 1
for num in nums {
if num >= 0 {
results.append(index)
}
index += 1
}
return results
}
}
缺點
- 需要宣告轉換成 mutable array ,和官方解法不同的多了 O(n) 的空間複雜度。
解法 3
看了解法 2 後才想到這個寫法
邏輯上和解法 1 相近,但是少了移除元素這個對 leetcode 的 Swift 比較耗時的操作,執行時間反而是裡面最短的
- 將 nums 轉換成 Set
- 走訪 1 到 nums.count 檢查是否有在 set 裡面出現,否則加入 result array
class Solution {
func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
guard !nums.isEmpty else { return [] }
var set = Set(nums)
var results = [Int]()
for num in 1...nums.count {
if !set.contains(num) {
results.append(num)
}
}
return results
}
}
後記
利用 index 標記出現位置的作法目前對自己來說還沒那麼直觀,接著要來找看看類似題目來做。
另外途中有試著用 Swift 高階函式寫,不過送出後執行速度果不其然變得非常慢,在 leetcode 上還是要小心使用。
Discussion