剑指offer 专项突破版 57、值和下标之差都在给定的范围内

题目链接

• 这道题的本质就是在问：数组中是否存在这样两个元素，满足如下两个条件
  1. 间距 ≤ k
  2. 差值 ≤ t
• 那么最朴素的想法就是暴力法，在思考暴力法的过程中也有两点值得注意
  • 对于某个元素，我们搜索时并不用和其余n-1个元素都比较，比较前后k个即可
  • 具体的搜索过程中，也不用前后都比较，对于遍历到的每个元素 都只和后面的k个元素或前面的k个元素比较即可
  • 基于上述假设的暴力法，时间复杂度为O(nk)

改进

• 我们发现对于每个元素，在和后面的k个元素比较的过程中，耗时的地方就是比较k次，既然我们的要求是差值≤k，那么如果能找到比该元素大的最小的值和比该元素小的最大的值，计算该元素和他们的差值。
  

  
  

  如果这样都不满足，那么其余的k-2个元素肯定也不满足！

• 那么既然这样，我们可以用TreeSet来保存前面的k个元素，通过floor和ceil函数获取我们想要的结果即可~ 这样每个元素的比较过程只需要logk的时间
• 与此同时，我们还要及时更新TreeSet中的值~

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            Long high = set.ceiling((long)nums[i]);
            if (null != high && high - nums[i] <= t)
                return true;

            Long low = set.floor((long)nums[i]);
            if (null != low && nums[i] - low <= t)
                return true;

            set.add((long)nums[i]);
            if (i >= k)
                set.remove((long)nums[i - k]);
        }
        return false;
    }
}

再度改进

• 利用桶我们可以在O(1)的时间内判断出是否有差值≤k的元素

• 现在假设我们有无数个按顺序编号的桶，每个桶都用来装不同范围的数字，每个桶承载范围的距离是t

  桶编号	数字范围(闭区间)
  0	0 —— t
  1	t+1 —— 2t+1
  2	2t+2 —— 3t+2
  -1	-1-t —— -1
  -2	-2-2t —— -2-t

  • 对于某个正数m，他和桶编号的映射函数为 m / (t+1)
  • 对于某个负数m，他和桶编号的映射函数为 (m+1)/(t+1) - 1

• 知道了具体的映射关系，我们在拿到一个数后，先把他映射到对应编号的桶中，然后检查桶中是否有元素，如果有，那么这两个元素的差值一定≤t，如果没有，还要判断相邻编号的桶中是否有元素并计算差值

• 与此同时还要记得在遍历时及时更新桶中的元素~

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        Map<Long, Integer> bucket = new HashMap<>();
        long bucketSize = t + 1;

        for (int i = 0; i < nums.length; i++) {
            long id = getId(nums[i],bucketSize);

            if (bucket.containsKey(id)
                    || bucket.containsKey(id - 1) && Math.abs((long) nums[bucket.get(id - 1)] - nums[i]) <= t
                    || bucket.containsKey(id + 1) && Math.abs((long) nums[bucket.get(id + 1)] - nums[i]) <= t)
                return true;

            bucket.put(id, i);

            if (i >= k)
                bucket.remove(getId(nums[i-k],bucketSize));
        }
        return false;
    }
    private long getId(int num, long bucketSize) {
        return num >= 0 ? num / bucketSize : (num + 1) / bucketSize - 1;
    }
}

这样做的话，每次在O(1)的时间内即可判断所以时间复杂度为O(n),空间复杂度为O(k)