难度: Medium
原题连接
内容描述
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
这道题虽然看似简单，但是我还是经历几次失败
第一次我打算用最粗暴的方法来做，直接 Time Limit Exceeded
然后我打算用第 219 题的方法来一遍，还是报 Time Limit Exceeded 这个错，代码如下L：
class Solution:
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
lookup = {}
for i in range(len(nums)):
if any(i - v <= k and abs(nums[i] - key) <= t for key, v in lookup.items()):
return True
else:
lookup[nums[i]] = i
return False
思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
最后我分情况讨论勉强AC
class Solution:
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
n = len(nums)
if t == 0:
lookup = collections.defaultdict(list)
for i, num in enumerate(nums):
lookup[num].append(i)
for key, v in lookup.items():
if len(v) >= 2:
for i in range(len(v)):
for j in range(i+1, len(v)):
if abs(v[j] - v[i]) <= k:
return True
return False
if k >= n:
for i in range(n):
for j in range(i+1, n):
if abs(nums[j] - nums[i]) <= t:
return True
else:
for i in range(n-k):
for j in range(1, k+1):
if abs(nums[i+j] - nums[i]) <= t:
return True
for i in range(n-k, n):
for j in range(i+1, n):
if abs(nums[j] - nums[i]) <= t:
return True
return False思路 3 - 时间复杂度: O(N * K)- 空间复杂度: O(1)******
我想到对于当前元素，我只需要跟它之前出现的k个元素相比即可，但还是超时
class Solution:
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
for i in range(len(nums)):
for j in range(max(i-k, 0), i):
if abs(nums[i] - nums[j]) <= t:
return True
return False
思路 4 - 时间复杂度: O(N * lg(min(N, K)))- 空间复杂度: O(min(N, K))******
对于思路三，我想了一下，觉得可以优化一下第二个for 循环，我完全可以用一个BST来实现快速的查找
然后这个BST里面永远只有k个元素，我们每次只需要找到一个最小的大于等于num的数字suceesor，一个最大的小于等于num的数字predecessor， 然后看看他们是否满足num - predecessor <= t或者(sucessor - num) <= t，任意一个满足就返回True，如果都不满足就将num插入到BST中， 再将之前的第k个元素即最老的那个元素remove掉，继续判断即可
AVL树实现完全copy from Python balanced BST solution
class Node(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1
class AVLTree(object):
def __init__(self):
self.root = None
self.size = 0
def height(self, node):
if node:
return node.height
return 0
def setHeight(self, node):
if node is None:
return 0
return 1 + max(self.height(node.left), self.height(node.right))
def rightRotate(self, node):
new_root = node.left
node.left = node.left.right
new_root.right = node
node.height = self.setHeight(node)
new_root.height = self.setHeight(new_root)
return new_root
def leftRotate(self, node):
new_root = node.right
node.right = node.right.left
new_root.left = node
node.height = self.setHeight(node)
new_root.height = self.setHeight(new_root)
return new_root
def insert(self, node, val):
if node == self.root:
self.size += 1
# Returns a Node pointing to updated subtree
if node is None:
return Node(val)
if node.val < val:
node.right = self.insert(node.right, val)
else:
node.left = self.insert(node.left, val)
balance = self.height(node.left) - self.height(node.right)
if balance > 1:
if self.height(node.left.left) > self.height(node.left.right):
node = self.rightRotate(node)
else:
node.left = self.leftRotate(node.left)
node = self.rightRotate(node)
elif balance < -1:
if self.height(node.right.right) > self.height(node.right.left):
node = self.leftRotate(node)
else:
node.right = self.rightRotate(node.right)
node = self.leftRotate(node)
else:
node.height = self.setHeight(node)
return node
def getMinValNode(self, node):
if node is None or node.left is None:
return node
return self.getMinValNode(node.left)
def remove(self, node, val):
if node is None:
return None
if node.val < val:
node.right = self.remove(node.right, val)
elif node.val > val:
node.left = self.remove(node.left, val)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
right_min_val_node = self.getMinValNode(node.right)
node.val = right_min_val_node.val
node.right = self.remove(node.right, right_min_val_node.val)
node.height = self.setHeight(node)
balance = self.height(node.left) - self.height(node.right)
if balance > 1:
if self.height(node.left.left) > self.height(node.left.right):
node = self.rightRotate(node)
else:
node.left = self.leftRotate(node.left)
node = self.rightRotate(node)
elif balance < -1:
if self.height(node.right.right) > self.height(node.right.left):
node = self.leftRotate(node)
else:
node.right = self.rightRotate(node.right)
node = self.leftRotate(node)
else:
node.height = self.setHeight(node)
return node
def predecessor(self, node, val):
if node is None:
return None
if node.val == val:
return val
elif node.val > val:
return self.predecessor(node.left, val)
else:
right_res = self.predecessor(node.right, val)
return right_res if right_res else node.val
def successor(self, node, val):
if node is None:
return None
if node.val == val:
return val
elif node.val < val:
return self.successor(node.right, val)
else:
left_res = self.successor(node.left, val)
return left_res if left_res else node.val
class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
avltree = AVLTree()
root = avltree.root
for i, num in enumerate(nums):
predecessor = avltree.predecessor(root, num) # greatest element in BST that is less than or equal to num
if predecessor is not None and num - predecessor <= t: # 一定要用 is not None, 因为就算返回 0 也是满足的
return True
successor = avltree.successor(root, num) # smallest element in BST that is greater than or equal to num
if successor is not None and successor - num <= t: # 一定要用 is not None, 因为就算返回 0 也是满足的
return True
root = avltree.insert(root, num)
if avltree.size > k:
root = avltree.remove(root, nums[i-k])
return False思路 5 - 时间复杂度: O(N)- 空间复杂度: O(min(N, K))******
Bucket Sort, 参考
class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
width = t + 1
if width <= 0:
return False
lookup = {}
for i in range(len(nums)):
bucket = nums[i] // width
if bucket in lookup:
return True
if bucket - 1 in lookup and abs(nums[i] - lookup[bucket - 1]) < width:
return True
if bucket + 1 in lookup and abs(nums[i] - lookup[bucket + 1]) < width:
return True
lookup[bucket] = nums[i]
if i >= k:
del lookup[nums[i - k] // width]
return Falseclass Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
width = t + 1
if width <= 0:
return False
lookup = collections.OrderedDict()
for n in nums:
key = n // width
# each bucket will always have at most element, otherwise it will return True before
for m in (lookup.get(key - 1), lookup.get(key), lookup.get(key + 1)):
if m is not None and abs(n - m) <= t:
return True
lookup[key] = n
if len(lookup) > k:
lookup.popitem(last = False)
return False