0220._Contains_Duplicate_III.md

220. Contains Duplicate III

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/contains-duplicate-iii/

内容描述

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, 参考

1. Solution
2. Java/Python one pass solution, O(n) time O(n) space using buckets
3. Python OrderedDict

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 False

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 = 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