Leetcode: 448. Find All Numbers Disappeared in an Array
Naive solution
- Primary idea: Check every number between 1 .. n if they are in the given array.
- Time Complexity: O(n*n)
- Space Complexity: O(n)
func native_findDisappearedNumbers(_ nums: [Int]) -> [Int] {
var result = [Int]()
for i in 1...nums.count {
if !nums.contains(i) {
result.append(i)
}
}
return result
}
print(findDisappearedNumbers([4,3,2,7,8,2,3,1])) // [5,6]
print(hasing_findDisappearedNumbers([1,1])) // 2Hashing solution
- Primary idea: The very basic idea is to use an array to store the frequency of each element in the given array. The number with a frequency of 0 is the missing number.
- Time Complexity: O(n)
- Space Complexity: O(n)
func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
var arr = Array(repeating: 0, count: nums.count)
var rs: [Int] = []
for i in 0..<nums.count {
arr[nums[i]-1] = 1
}
for i in 0..<nums.count {
if arr[i] == 0 {
rs.append(i+1)
}
}
return rs
}
print(findDisappearedNumbers([4,3,2,7,8,2,3,1])) // [5,6]
print(hasing_findDisappearedNumbers([1,1])) // 2