220. 存在重复元素 III [medium]

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

在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。

如果存在则返回 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

通过次数20,213 | 提交次数76,662

Second Try

2020-07-14

虽然知道可以使用bucket桶排序，但是还是有很多细节，写的时候头疼还要去参考题解
使用bucket，但并不是事先设置好列表的那种，而是字典类型
但不只在桶里的元素会满足距离小于k的条件，桶的前后桶也有满足的才对。
最大的疑惑是如果一个桶里有多个元素，岂不是还要和前后两个桶进行遍历筛选？
解决方法是：每个桶最多只有一个元素，如果放进去的时候已经存在其他元素，则返回结果已经确定
还有一个问题是如何保证隔壁桶的距离都在k之内？每次岂不是又要判断一遍
解决方法是对于距离k的问题，每次都会对超过距离k的元素进行筛除，保证只要桶里有元素，就符合距离要求

复杂度竟然只有O(n), 算是第一次写出了bucket排序相关的。

class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """

        if k <= 0 or t < 0:  # 这竟然也要处理。。。
            return False 

        buckets = dict()
        for idx, n in enumerate(nums):
            # print(idx, n, buckets)
            bid = n // (t + 1)  # t + 1内任意元素间隔小于等于t
            if bid in buckets:
                return True 
            if bid - 1 in buckets and abs(buckets[bid - 1] - n) <= t:
                return True 
            if bid + 1 in buckets and abs(buckets[bid + 1] - n ) <= t:
                return True 
            if idx >= k:  # 毕竟0-k的话，还不需要剔除0；距离小于等于k，表示可以放k + 1个元素
                buckets.pop(nums[idx - k] // (t + 1))          
            buckets[bid] = n
        return False 

执行用时：32 ms, 在所有 Python 提交中击败了58.56%的用户
内存消耗：13.9 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-07-14

普通的O(n * k)算法超时了，但看题解也有通过的，也就是额外对k=1和t=0的情况进行额外处理，结果竟然快得排名前列了。但从通用编程角度看，这个并不是标准复杂度的解法吧。

class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        # 提供其他补充措施，针对案例编程...
        if k == 1:
            for i in range(1, len(nums)):
                if abs(nums[i] - nums[i-1]) <= t:
                    return True
            return False 

        if t == 0:
            nearest = dict()
            for idx, n in  enumerate(nums):
                if n in nearest:
                    if n - nearest[n] <= k:
                        return True 
                nearest[n] = idx
            return False 

        # O(n^2)的写法，果然超时了。。。 但其实应该是O(N * k),连这都要超时吗
        n = len(nums)
        for i in range(n - 1):
            for j in range(i + 1, n):
                if j - i > k:
                    break 
                if abs(nums[i] - nums[j]) <= t:
                    return True 
        return False 

执行用时：20 ms, 在所有 Python 提交中击败了97.24%的用户
内存消耗：14 MB, 在所有 Python 提交中击败了100.00%的用户

220. 存在重复元素 III [medium]​

Second Try​

First Try​

220. 存在重复元素 III [medium]

Second Try

First Try