哈希
以下为 LeetCode 哈希 相关问题解法记录。
问题分析：暂时未找到最优解法。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
var hash: [Int] = []
for _ in 0..<nums.count {
hash.append(0)
}
for i in nums {
hash[i - 1] = 1
}
var result: [Int] = []
for (index, value) in hash.enumerated() {
if value == 0 {
result.append(index + 1)
}
}
return result
}
}
|
状态：优于40%的提交。
问题分析：该问题可转化为给定一个数，查找与另一个数的差是否存在，即查找问题。
方法一：每次遍历查找，时间复杂度O(n2)。
方法二：将数组元素i标记为 map[num[i]] = i ，通过下标索引，将查找复杂度由 O(n) 将为 O(1) ，空间复杂度为 O(n) 。
方法三：边建立哈希表边检查是否存在对应元素，因为是成对的，开始没有找到，之后也会找到，一遍循环搞定。
代码：
1
2
3
4
5
| class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
}
}
|
启发：需要对 查找 常用方法进行加深学习。
问题分析：哈希。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
func containsDuplicate(_ nums: [Int]) -> Bool {
var dict: [Int : Int] = [:]
for i in nums {
if dict[i] == nil {
dict[i] = 1
} else {
dict[i]! = dict[i]! + 1
}
if dict[i]! > 1 {
return true
}
}
return false
}
}
|
启发：字典取值需要判断是否为空。
状态：优于52%的提交。
问题分析：哈希表。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
func missingNumber(_ nums: [Int]) -> Int {
var hash: [Int] = []
for i in 0...nums.count {
hash.append(0)
}
for i in nums {
hash[i] = 1
}
for (i,value) in hash.enumerated() {
if value == 0 {
return i
}
}
return 0
}
}
|
思考：如何用常数额外空间O(n)时间复杂度解决？