😶‍🌫️

448. Find All Numbers Disappeared in an Array

2022/10/30に公開

題目

解法 1 - Hash Set

看完題目後第一個想到的解法

  1. 宣告一個 set 列出 1 到 n
  2. 走訪 array nums ,移除有出現過的數字
  3. 轉換成 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 比較耗時的操作,執行時間反而是裡面最短的

  1. 將 nums 轉換成 Set
  2. 走訪 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