class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
}
};
220. 存在重复元素 III
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0 输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2 输出：true
示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3 输出：false
提示：
0 <= nums.length <= 2 * 104-231 <= nums[i] <= 231 - 10 <= k <= 1040 <= t <= 231 - 1原站题解
python3 解法, 执行用时: 164 ms, 内存消耗: 25.6 MB, 提交时间: 2022-11-22 10:31:11
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
'''
我们按照元素的大小进行分桶，维护一个滑动窗口内的元素对应的元素
'''
def getId(x: int, w: int) -> int:
if x >= 0:
return x // w
return (x+1) // w - 1
mp = dict()
for i, x in enumerate(nums):
_id = getId(x, t+1)
if _id in mp: return True
if _id - 1 in mp and abs(x-mp[_id-1]) <= t: return True
if _id + 1 in mp and abs(x-mp[_id+1]) <= t: return True
mp[_id] = x
if i >= k:
mp.pop(getId(nums[i-k], t+1))
return False
golang 解法, 执行用时: 100 ms, 内存消耗: 8.5 MB, 提交时间: 2022-11-22 10:18:01
func getID(x, w int) int {
if x >= 0 {
return x / w
}
return (x+1)/w - 1
}
func containsNearbyAlmostDuplicate(nums []int, k, t int) bool {
mp := map[int]int{}
for i, x := range nums {
id := getID(x, t+1)
if _, has := mp[id]; has {
return true
}
if y, has := mp[id-1]; has && abs(x-y) <= t {
return true
}
if y, has := mp[id+1]; has && abs(x-y) <= t {
return true
}
mp[id] = x
if i >= k {
delete(mp, getID(nums[i-k], t+1))
}
}
return false
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
golang 解法, 执行用时: 124 ms, 内存消耗: 8.7 MB, 提交时间: 2022-11-22 10:17:24
import "math/rand"
type node struct {
ch [2]*node
priority int
val int
}
func (o *node) cmp(b int) int {
switch {
case b < o.val:
return 0
case b > o.val:
return 1
default:
return -1
}
}
func (o *node) rotate(d int) *node {
x := o.ch[d^1]
o.ch[d^1] = x.ch[d]
x.ch[d] = o
return x
}
type treap struct {
root *node
}
func (t *treap) _put(o *node, val int) *node {
if o == nil {
return &node{priority: rand.Int(), val: val}
}
d := o.cmp(val)
o.ch[d] = t._put(o.ch[d], val)
if o.ch[d].priority > o.priority {
o = o.rotate(d ^ 1)
}
return o
}
func (t *treap) put(val int) {
t.root = t._put(t.root, val)
}
func (t *treap) _delete(o *node, val int) *node {
if d := o.cmp(val); d >= 0 {
o.ch[d] = t._delete(o.ch[d], val)
return o
}
if o.ch[1] == nil {
return o.ch[0]
}
if o.ch[0] == nil {
return o.ch[1]
}
d := 0
if o.ch[0].priority > o.ch[1].priority {
d = 1
}
o = o.rotate(d)
o.ch[d] = t._delete(o.ch[d], val)
return o
}
func (t *treap) delete(val int) {
t.root = t._delete(t.root, val)
}
func (t *treap) lowerBound(val int) (lb *node) {
for o := t.root; o != nil; {
switch c := o.cmp(val); {
case c == 0:
lb = o
o = o.ch[0]
case c > 0:
o = o.ch[1]
default:
return o
}
}
return
}
func containsNearbyAlmostDuplicate(nums []int, k, t int) bool {
set := &treap{}
for i, v := range nums {
if lb := set.lowerBound(v - t); lb != nil && lb.val <= v+t {
return true
}
set.put(v)
if i >= k {
set.delete(nums[i-k])
}
}
return false
}