-
Notifications
You must be signed in to change notification settings - Fork 0
/
220.swift
135 lines (122 loc) · 4.34 KB
/
220.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// passed but slow
class Solution {
// 折半查找 返回相等或者第一个大于目标的 index
func containsNearbyAlmostDuplicate(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
var pool = [Int]()
func indexToInsert(num: Int) -> Int {
// 问题:找到数组中第一个大于等于 num 的数的 index
// 没找到的话,返回 pool.count
guard pool.count > 0 else { return 0 }
var l = 0
var r = pool.count-1
while l<r {
let m = (l+r)/2
if pool[m] == num {
return m
} else if pool[m] < num {
l = m + 1
} else {
if m > 0, pool[m-1] < num {
return m
} else if m == 0 {
return m
} else {
r = m
}
}
}
return pool[r] < num ? r + 1 : r
}
for i in 0..<nums.count {
if i > k {
let iToRemove = indexToInsert(num: nums[i-k-1])
pool.remove(at: iToRemove)
}
let index = indexToInsert(num: nums[i])
if (index > 0 && nums[i] - pool[index-1] <= t) ||
(index < pool.count && pool[index] - nums[i] <= t) {
// it's pool.count NOT pool.count - 1, because pool is short by 1 by now.
// AND pool[indexToInsert] NOT pool[indexToInsert+1] for the same reason
return true
}
pool.insert(nums[i], at: index)
}
return false
}
}
class Solution1 {
// 暴力法:遍历所有 pairs O(n^2)
// 优化:对于每一个i,只需要向后找k个 O(n*k)
// 超时失败
func containsNearbyAlmostDuplicate(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
guard k>0 else { return false }
for i in 0..<(nums.count - 1) {
for j in i+1..<min(nums.count, i+k+1) {
if abs(nums[i] - nums[j]) <= t {
return true
}
}
}
return false
}
}
class Solution2 {
// 先不排序,维护一个大小为k的排序数组,判断新插入的数字与邻居的距离
// 先试试不使用折半查找的简化版 依然超时!!
func containsNearbyAlmostDuplicate(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
var pool = [Int]()
for i in 0..<nums.count {
if i > k {
pool.removeAll { $0 == nums[i-k-1] } // It will always be 1.
}
let indexToInsert = pool.firstIndex { $0 > nums[i] } ?? pool.endIndex
if (indexToInsert > 0 && nums[i] - pool[indexToInsert-1] <= t) ||
(indexToInsert < pool.count && pool[indexToInsert] - nums[i] <= t) {
// it's pool.count NOT pool.count - 1, because pool is short by 1 by now.
// AND pool[indexToInsert] NOT pool[indexToInsert+1] for the same reason
return true
}
pool.insert(nums[i], at: indexToInsert)
}
return false
}
}
// from others
class Solution {
func containsNearbyAlmostDuplicate(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
return solution1(nums, k, t)
}
}
// O(N^2)
extension Solution {
func solution1(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
guard nums.count > 1 else { return false }
if t == 0 {
return duplicateAtDistance(nums, k)
} else {
return quadraticSolution(nums, k, t)
}
}
func duplicateAtDistance(_ nums: [Int], _ k: Int) -> Bool {
var dict: [Int: Int] = [:]
for i in 0..<nums.count {
if let j = dict[nums[i]], i - j <= k {
return true
} else {
dict[nums[i]] = i
}
}
return false
}
func quadraticSolution(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
guard nums.count > 1 else { return false }
for i in 0..<nums.count {
for j in 0..<nums.count where abs(i - j) <= k && i != j {
if abs(nums[i] - nums[j]) <= t {
return true
}
}
}
return false
}
}