Leetcode: 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 difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

暴力枚举会LTE，解题思路是用sortedSet来解决，sortedSet可以返回一个在某个范围的subSet，同时判断这个subSet是否为空即可解决，主要，本题需要使用long类型！

 1 public class Solution {
 2     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 3         if (nums==null || nums.length<2 || k<1 || t<0) return false;
 4         SortedSet<Long> set = new TreeSet<Long>();
 5         for (int i=0; i<nums.length; i++) {
 6             long lowerBound = (long)nums[i]-t;
 7             long upperBound = (long)nums[i]+t+1;
 8             SortedSet<Long> temp = set.subSet(lowerBound, upperBound);
 9             if (!temp.isEmpty()) {
10                 return true;
11             }
12             set.add((long)nums[i]);
13             if (set.size() > k) set.remove((long)nums[i-k]);
14             
15         }
16         return false;
17     }
18 }

时间 O(NlogK) 空间 O(K)

思路

要求判断之前是否存在差值小于t的数字，我们需要知道在当前数字x两边的数字，即最大的小于x的数字和最小的大于x的数字。二叉搜索树有也有这样的性质，它的左子树的最右节点是最大的较小值，右子树的最左节点是最小的较大值。这里我们用TreeSet这个类，它实现了红黑树，并有集合的性质，非常适合这题。我们同样也是维护一个大小为k的TreeSet，多余k个元素时把最早加入的给删除。用ceiling()和floor()可以找到最小的较大值和最大的较小值。

 1 public class Solution {
 2     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 3         TreeSet<Integer> set = new TreeSet<Integer>();
 4         for(int i = 0; i < nums.length; i++){
 5             int x = nums[i];
 6             // 最小的大于x的数字
 7             if(set.ceiling(x) != null && set.ceiling(x) <= t + x) return true;
 8             // 最大的小于x的数字
 9             if(set.floor(x) != null && x <= t + set.floor(x)) return true;
10             set.add(x);
11             if(set.size()>k) set.remove(nums[i-k]);
12         }
13         return false;
14     }
15 }

关于TreeSet 和HashSet 比较：

HashSet is much faster than TreeSet (constant-time versus log-time for most operations like add, remove and contains) but offers no ordering guarantees like TreeSet.

HashSet

class offers constant time performance for the basic operations (add, remove, contains and size).
it does not guarantee that the order of elements will remain constant over time
iteration performance depends on the initial capacity and the load factor of the HashSet.
- It's quite safe to accept default load factor but you may want to specify an initial capacity that's about twice the size to which you expect the set to grow.

TreeSet

guarantees log(n) time cost for the basic operations (add, remove and contains)
guarantees that elements of set will be sorted (ascending, natural, or the one specified by you via its constructor) (implements SortedSet)
doesn't offer any tuning parameters for iteration performance
offers a few handy methods to deal with the ordered set like first(), last(), headSet(), and tailSet() etc（本题就用了ceiling()和flooring()两个method）

非常好的方法：Bucket

just make sure the size of the bucket is reasonable such that elements having the same bucket is immediately considered duplicates or duplicates must lie within adjacent buckets. So this actually gives us a range of possible bucket size, i.e. t and t + 1. We just choose it to be t and a bucket mapping to be num / t.

https://discuss.leetcode.com/topic/15199/ac-o-n-solution-in-java-using-buckets-with-explanation

 1  public class Solution {
 2     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 3         if (k < 1 || t < 0) return false;
 4         Map<Long, Long> map = new HashMap<>();
 5         for (int i = 0; i < nums.length; i++) {
 6             long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
 7             long bucket = remappedNum / ((long) t + 1);
 8             if (map.containsKey(bucket)
 9                     || (map.containsKey(bucket - 1) && remappedNum - map.get(bucket - 1) <= t)
10                         || (map.containsKey(bucket + 1) && map.get(bucket + 1) - remappedNum <= t))
11                             return true;
12             if (map.entrySet().size() >= k) {
13                 long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1);
14                 map.remove(lastBucket);
15             }
16             map.put(bucket, remappedNum);
17         }
18         return false;
19     }
20 }