220. 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.

解法1： TreeSet, O(nlog(k, n))

这里用到一个比较特殊的数据结构treeset。
实际上这是一个self-balancing binary search tree, 他的基本操作都是O(logN)的。而且他还有两个额外的功能很有用
set.ceiling(T)和set.floor(T)
ceiling返回的是大于等于T的最小的元素，而floor返回的是小于等于T的最大元素。
那么我们维护一个大小为k的set，这样就满足了一个条件。
那第二个条件满足的条件就是对于每一个num，找出他的ceiling和floor，看是否在范围内即可。

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            int current = nums[i];
            Integer ceiling = set.ceiling(current);
            Integer floor = set.floor(current);
            if (ceiling != null && ceiling <= current + t) {
                return true;
            }
            if (floor != null && current <= floor + t) {
                return true;
            }
            set.add(current);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

解法2： O(N) using Bucket

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    private long getBucketId(long num, long w) {
        return num < 0 ? (num + 1) / w - 1 : num / w;
    }
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (t < 0 ) return false;
        if (nums == null || nums.length == 0) {
            return false;
        }    
        long w = (long)t + 1;
        Map<Long, Long> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            long id = getBucketId((long)nums[i], w);
            if (map.containsKey(id)) {
                return true;
            }
            if (map.containsKey(id - 1) && Math.abs(map.get(id - 1) - nums[i]) < w) {
                return true;
            }
            if (map.containsKey(id + 1) && Math.abs(map.get(id + 1) - nums[i]) < w) {
                return true;
            }
            map.put(id, (long)nums[i]);
            if (i >= k) {
                map.remove(getBucketId(nums[i - k], w));
            }
        }
        return false;
    }
}