Skip to content

Commit ebebf5c

Browse files
halfrosthalfrost
committed
Modify solution 220
1 parent e172b5e commit ebebf5c

File tree

3 files changed

+62
-65
lines changed

3 files changed

+62
-65
lines changed

‎leetcode/0220.Contains-Duplicate-III/220. Contains Duplicate III.go

Lines changed: 31 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -1,51 +1,38 @@
11
package leetcode
22

3-
import "sort"
4-
5-
// 解法一 排序 + 滑动窗口
3+
// 解法一 桶排序
64
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
7-
if len(nums) < 2 {
5+
if k <= 0 || t < 0 || len(nums) < 2 {
86
return false
97
}
10-
elemList := make([]*elem, len(nums))
11-
for i, num := range nums {
12-
elemList[i] = &elem{num, i}
13-
}
14-
sort.SliceStable(elemList, func(i, j int) bool {
15-
if elemList[i].val != elemList[j].val {
16-
return elemList[i].val < elemList[j].val
8+
buckets := map[int]int{}
9+
for i := 0; i < len(nums); i++ {
10+
// Get the ID of the bucket from element value nums[i] and bucket width t + 1
11+
key := nums[i] / (t + 1)
12+
// -7/9 = 0, but need -7/9 = -1
13+
if nums[i] < 0 {
14+
key--
1715
}
18-
return elemList[i].idx < elemList[j].idx
19-
})
20-
i, j := 0, 1
21-
for j < len(elemList) {
22-
if elemList[j].val-elemList[i].val <= t {
23-
if abs(elemList[j].idx-elemList[i].idx) <= k {
24-
return true
25-
}
26-
j++
27-
} else {
28-
i++
29-
if j <= i {
30-
j++
31-
}
16+
if _, ok := buckets[key]; ok {
17+
return true
18+
}
19+
// check the lower bucket, and have to check the value too
20+
if v, ok := buckets[key-1]; ok && nums[i]-v <= t {
21+
return true
3222
}
23+
// check the upper bucket, and have to check the value too
24+
if v, ok := buckets[key+1]; ok && v-nums[i] <= t {
25+
return true
26+
}
27+
// maintain k size of window
28+
if len(buckets) >= k {
29+
delete(buckets, nums[i-k]/(t+1))
30+
}
31+
buckets[key] = nums[i]
3332
}
3433
return false
3534
}
3635

37-
func abs(a int) int {
38-
if a > 0 {
39-
return a
40-
}
41-
return -a
42-
}
43-
44-
type elem struct {
45-
val int
46-
idx int
47-
}
48-
4936
// 解法二 滑动窗口 + 剪枝
5037
func containsNearbyAlmostDuplicate1(nums []int, k int, t int) bool {
5138
if len(nums) <= 1 {
@@ -66,3 +53,10 @@ func containsNearbyAlmostDuplicate1(nums []int, k int, t int) bool {
6653
}
6754
return false
6855
}
56+
57+
func abs(a int) int {
58+
if a > 0 {
59+
return a
60+
}
61+
return -a
62+
}

‎leetcode/0220.Contains-Duplicate-III/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,3 +32,4 @@ Given an array of integers, find out whether there are two distinct indices i 
3232
- 给出一个数组，要求在数组里面找到 2 个索引，`i` 和 `j`，使得 `| nums[i] - nums[j] | ≤ t` ，并且 `| i - j | ≤ k` 。
3333
- 这是一道滑动窗口的题目。第一想法就是用 `i` 和 `j` 两个指针，针对每个 `i` ，都从 `i + 1` 往后扫完整个数组，判断每个 `i` 和 `j` ，判断是否满足题意。`j` 在循环的过程中注意判断剪枝条件 `| i - j | ≤ k`。这个做法的时间复杂度是 O(n^2)。这个做法慢的原因在于滑动窗口的左边界和右边界在滑动过程中不是联动滑动的。
3434
- 于是考虑，如果数组是有序的呢？把数组按照元素值从小到大进行排序，如果元素值相等，就按照 index 从小到大进行排序。在这样有序的数组中找满足题意的 `i` 和 `j`，滑动窗口左边界和右边界就是联动的了。窗口的右边界滑到与左边界元素值的差值 ≤ t 的地方，满足了这个条件再判断 `| i - j | ≤ k`，如果右边界与左边界元素值的差值 > t 了，说明该把左边界往右移动了(能这样移动的原因就是因为我们将数组元素大小排序了，右移是增大元素的方向)。移动左边界的时候需要注意左边界不能超过右边界。这样滑动窗口一次滑过整个排序后的数组，就可以判断是否存在满足题意的 `i` 和 `j` 。这个做法的时间主要花在排序上了，时间复杂度是 O(n log n)。
35+
- 本题最优解是利用桶排序的思想。`| i - j | ≤ k` 这个条件利用一个窗口大小为 k 来维护。重点在 `| nums[i] - nums[j] | ≤ t` 这个条件如何满足。利用桶排序的思想，将 `nums[i]` 所有元素分为 ...,`[0,t]`,`[t+1,2t+1]`,...。每个区间的大小为 `t + 1`。每个元素现在都对应一个桶编号。进行 3 次查找即可确定能否找到满足这个 `| nums[i] - nums[j] | ≤ t` 条件的数对。如果在相同的桶中找到了元素，那么说明能找到这样的 i 和 j。还有 2 种可能对应桶边界的情况。如果存在前一个桶中的元素能使得相差的值也 `≤ t`，这样的数对同样满足题意。最后一种情况是，如果存在后一个桶中的元素能使得相差的值也 `≤ t`，这样的数对同样满足题意。查询 3 次，如果都不存在，说明当前的 i 找不到满足题意的 j。继续循环寻找。循环一遍都找不到满足题意的数对，输出 false。

‎website/content/ChapterFour/0220.Contains-Duplicate-III.md

Lines changed: 30 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@ Given an array of integers, find out whether there are two distinct indices i 
3232
- 给出一个数组，要求在数组里面找到 2 个索引，`i` 和 `j`，使得 `| nums[i] - nums[j] | ≤ t` ，并且 `| i - j | ≤ k` 。
3333
- 这是一道滑动窗口的题目。第一想法就是用 `i` 和 `j` 两个指针，针对每个 `i` ，都从 `i + 1` 往后扫完整个数组，判断每个 `i` 和 `j` ，判断是否满足题意。`j` 在循环的过程中注意判断剪枝条件 `| i - j | ≤ k`。这个做法的时间复杂度是 O(n^2)。这个做法慢的原因在于滑动窗口的左边界和右边界在滑动过程中不是联动滑动的。
3434
- 于是考虑，如果数组是有序的呢？把数组按照元素值从小到大进行排序，如果元素值相等，就按照 index 从小到大进行排序。在这样有序的数组中找满足题意的 `i` 和 `j`，滑动窗口左边界和右边界就是联动的了。窗口的右边界滑到与左边界元素值的差值 ≤ t 的地方，满足了这个条件再判断 `| i - j | ≤ k`，如果右边界与左边界元素值的差值 > t 了，说明该把左边界往右移动了(能这样移动的原因就是因为我们将数组元素大小排序了，右移是增大元素的方向)。移动左边界的时候需要注意左边界不能超过右边界。这样滑动窗口一次滑过整个排序后的数组，就可以判断是否存在满足题意的 `i` 和 `j` 。这个做法的时间主要花在排序上了，时间复杂度是 O(n log n)。
35+
- 本题最优解是利用桶排序的思想。`| i - j | ≤ k` 这个条件利用一个窗口大小为 k 来维护。重点在 `| nums[i] - nums[j] | ≤ t` 这个条件如何满足。利用桶排序的思想，将 `nums[i]` 所有元素分为 ...,`[0,t]`,`[t+1,2t+1]`,...。每个区间的大小为 `t + 1`。每个元素现在都对应一个桶编号。进行 3 次查找即可确定能否找到满足这个 `| nums[i] - nums[j] | ≤ t` 条件的数对。如果在相同的桶中找到了元素，那么说明能找到这样的 i 和 j。还有 2 种可能对应桶边界的情况。如果存在前一个桶中的元素能使得相差的值也 `≤ t`，这样的数对同样满足题意。最后一种情况是，如果存在后一个桶中的元素能使得相差的值也 `≤ t`，这样的数对同样满足题意。查询 3 次，如果都不存在，说明当前的 i 找不到满足题意的 j。继续循环寻找。循环一遍都找不到满足题意的数对，输出 false。
3536

3637

3738
## 代码
@@ -40,43 +41,44 @@ Given an array of integers, find out whether there are two distinct indices i 
4041

4142
package leetcode
4243

43-
import "sort"
44-
45-
// 解法一 排序 + 滑动窗口
44+
// 解法一 桶排序
4645
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
47-
if len(nums) < 2 {
46+
if k <= 0 || t < 0 || len(nums) < 2 {
4847
return false
4948
}
50-
elemList := make([]*elem, len(nums))
51-
for i, num := range nums {
52-
elemList[i] = &elem{num, i}
53-
}
54-
sort.SliceStable(elemList, func(i, j int) bool {
55-
if elemList[i].val != elemList[j].val {
56-
return elemList[i].val < elemList[j].val
49+
buckets := map[int]int{}
50+
for i := 0; i < len(nums); i++ {
51+
// Get the ID of the bucket from element value nums[i] and bucket width t + 1
52+
key := nums[i] / (t + 1)
53+
// -7/9 = 0, but need -7/9 = -1
54+
if nums[i] < 0 {
55+
key--
5756
}
58-
return elemList[i].idx < elemList[j].idx
59-
})
60-
i, j := 0, 1
61-
for j < len(elemList) {
62-
if elemList[j].val-elemList[i].val <= t {
63-
if abs(elemList[j].idx-elemList[i].idx) <= k {
64-
return true
65-
}
66-
j++
67-
} else {
68-
i++
69-
if j <= i {
70-
j++
71-
}
57+
if _, ok := buckets[key]; ok {
58+
return true
7259
}
60+
// check the lower bucket, and have to check the value too
61+
if v, ok := buckets[key-1]; ok && nums[i]-v <= t {
62+
return true
63+
}
64+
// check the upper bucket, and have to check the value too
65+
if v, ok := buckets[key+1]; ok && v-nums[i] <= t {
66+
return true
67+
}
68+
// maintain k size of window
69+
if len(buckets) >= k {
70+
delete(buckets, nums[i-k]/(t+1))
71+
}
72+
buckets[key] = nums[i]
7373
}
7474
return false
7575
}
7676

77-
type elem struct {
78-
val int
79-
idx int
77+
func abs(a int) int {
78+
if a > 0 {
79+
return a
80+
}
81+
return -a
8082
}
8183

8284
// 解法二 滑动窗口 + 剪枝

0 commit comments

Comments
 (0)