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

链接： http://leetcode.com/problems/contains-duplicate-iii/

7/17/2017

不会做，抄答案

用TreeSet，找比nums[i]大的最小值和比它小的最大值来比较。注意第7，第11行，一定注意，不是s - nums[i] <= t, nums[i] - g <= t，为什么？

然而，这个算法还是有问题的，以下test case还是会出错：[2147483647, 1, 2147483647]，2，1。算来算去也只有bucket sort那个方法好像没有问题。

时间复杂度O(nlogk)

 1 public class Solution {
 2     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 3         TreeSet<Integer> ts = new TreeSet<>();
 4         for (int i = 0; i < nums.length; ++i) {
 5             // Find the successor of current element
 6             Integer s = ts.ceiling(nums[i]);
 7             if (s != null && s <= nums[i] + t) return true;
 8 
 9             // Find the predecessor of current element
10             Integer g = ts.floor(nums[i]);
11             if (g != null && nums[i] <= g + t) return true;
12 
13             ts.add(nums[i]);
14             if (ts.size() > k) {
15                 ts.remove(nums[i - k]);
16             }
17         }
18         return false;
19     }
20 }

官方解答，还有时间复杂度更好的bucket sort

https://leetcode.com/problems/contains-duplicate-iii/#/solution

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

别人的答案

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

下面这个treemap的实现是可以通过上面的test case

https://discuss.leetcode.com/topic/15191/java-o-n-lg-k-solution

https://discuss.leetcode.com/topic/27608/java-python-one-pass-solution-o-n-time-o-n-space-using-buckets