220. Contains Duplicate III

  • 19.3%

https://leetcode.com/problems/contains-duplicate-iii/?tab=Description

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.


需要思考

方法一:

因为需要有序,所以使用的set,set也有lower_bound相关函数

学习set,排序的set,学习low_bound函数使用

比较直接,使用了lower_bound, upper_bound

如果要存在,肯定在两者之间

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if(nums.empty() || k<=0 || t<0)
return false;
// 对于int,经常出现溢出,不如long long
set<long long> set;
for(int i=0; i<nums.size(); i++){
long long num = nums[i];
auto itlow = set.lower_bound(num-t);
auto itup = set.upper_bound(num+t);
// 此处的迭代器没有 <
if(itlow!=itup)
return true;
set.insert(num);
if(set.size()==k+1)
set.erase(nums[i-k]);
}
return false;
}
};

下面的算法有一定的公式推导,但是也比较简单,原理是一致的。

https://discuss.leetcode.com/topic/18453/c-using-set-less-10-lines-with-simple-explanation

C++ using set (less 10 lines), with simple explanation.

1
2
3
4
5
6
7
8
9
10
11
12
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<int> window; // set is ordered automatically
for (int i = 0; i < nums.size(); i++) {
if (i > k) window.erase(nums[i-k-1]); // keep the set contains nums i j at most k
// |x - nums[i]| <= t ==> -t <= x - nums[i] <= t;
auto pos = window.lower_bound(nums[i] - t); // x-nums[i] >= -t ==> x >= nums[i]-t
// x - nums[i] <= t ==> |x - nums[i]| <= t
if (pos != window.end() && *pos - nums[i] <= t) return true;
window.insert(nums[i]);
}
return false;
}

https://discuss.leetcode.com/topic/15468/i-finally-got-ac-in-c

I finally got AC in C++

Using a set container to keep the k+1-length array,which all elements are distinct.Before the container’s size reached k+1, we just find the first element that is not less than [nums[i]-t] and judge the element’s value whether it is less than [nums[i]+t]. Starting to move forward by erasing the head and adding element at the backend after the container’s size reached k+1. The existence of the first element ,which is not less than [nums[i]-t] and less than [nums[i]+t], is the prerequisite of existing other eligible elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
{
if (!k || t<0 || nums.size()<2)
return false;
set<int>record;
auto nLen = nums.size();
for (int i = 0; i < nLen;++i)
{
if (i>k)
record.erase(nums[i - k - 1]);
set<int>::iterator lower = record.lower_bound(nums[i] - t);
if (lower != record.end() && abs(nums[i] - *lower) <= t)
return true;

record.insert(nums[i]);
}
return false;
}

https://discuss.leetcode.com/topic/15172/accept-c-solution

Accept C++ Solution

My idea is to preserve a sliding window containing nearest k numbers, and check if next number collides to the numbers in the window.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (nums.size() < 2 || k == 0)
return false;
deque<int> windows_deq;
multiset<long> windows;
for (int i = 0; i < nums.size(); i++) {
if (windows.size() > k) {
int num = windows_deq.front();
windows_deq.pop_front();
windows.erase(windows.find(num));
}
auto it = windows.lower_bound((long)nums[i] - (long)t);
if (it == windows.end() || *it > (long)nums[i] + (long)t) {
// not found
windows_deq.push_back(nums[i]);
windows.insert(nums[i]);
}
else return true;
}
return false;
}
};

python


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

The idea is like the bucket sort algorithm. Suppose we have consecutive buckets covering the range of nums with each bucket a width of (t+1). If there are two item with difference <= t, one of the two will happen:

1
2
(1) the two in the same bucket
(2) the two in neighbor buckets

For detailed explanation see my blog here

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def containsNearbyAlmostDuplicate(self, nums, k, t):
if t < 0: return False
n = len(nums)
d = {}
w = t + 1
for i in xrange(n):
m = nums[i] / w
if m in d:
return True
if m - 1 in d and abs(nums[i] - d[m - 1]) < w:
return True
if m + 1 in d and abs(nums[i] - d[m + 1]) < w:
return True
d[m] = nums[i]
if i >= k: del d[nums[i - k] / w]
return False


# 30 / 30 test cases passed.
# Status: Accepted
# Runtime: 56 ms
# 93.81%

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private long getID(long i, long w) {
return i < 0 ? (i + 1) / w - 1 : i / w;
}

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) return false;
Map<Long, Long> d = new HashMap<>();
long w = (long)t + 1;
for (int i = 0; i < nums.length; ++i) {
long m = getID(nums[i], w);
if (d.containsKey(m))
return true;
if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)
return true;
if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)
return true;
d.put(m, (long)nums[i]);
if (i >= k) d.remove(getID(nums[i - k], w));
}
return false;
}

https://discuss.leetcode.com/topic/19991/o-n-python-using-buckets-with-explanation-10-lines

O(n) Python using buckets with explanation, 10 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def containsNearbyAlmostDuplicate(self, nums, k, t):
# Bucket sort. Each bucket has size of t. For each number, the possible
# candidate can only be in the same bucket or the two buckets besides.
# Keep as many as k buckets to ensure that the difference is at most k.
buckets = {}
for i, v in enumerate(nums):
# t == 0 is a special case where we only have to check the bucket
# that v is in.
bucketNum, offset = (v / t, 1) if t else (v, 0)
for idx in xrange(bucketNum - offset, bucketNum + offset + 1):
if idx in buckets and abs(buckets[idx] - nums[i]) <= t:
return True

buckets[bucketNum] = nums[i]
if len(buckets) > k:
# Remove the bucket which is too far away. Beware of zero t.
del buckets[nums[i - k] / t if t else nums[i - k]]

return False

https://discuss.leetcode.com/topic/15190/python-ordereddict

Python OrderedDict

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:

def containsNearbyAlmostDuplicate(self, nums, k, t):
if k < 1 or t < 0:
return False
dic = collections.OrderedDict()
for n in nums:
key = n if not t else n // t
for m in (dic.get(key - 1), dic.get(key), dic.get(key + 1)):
if m is not None and abs(n - m) <= t:
return True
if len(dic) == k:
dic.popitem(False)
dic[key] = n
return False

java


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

AC O(N) solution in Java using buckets with explanation

As a followup question, it naturally also requires maintaining a window of size k. When t == 0, it reduces to the previous question so we just reuse the solution.

Since there is now a constraint on the range of the values of the elements to be considered duplicates, it reminds us of doing a range check which is implemented in tree data structure and would take O(LogN) if a balanced tree structure is used, or doing a bucket check which is constant time. We shall just discuss the idea using bucket here.

Bucketing means we map a range of values to the a bucket. For example, if the bucket size is 3, we consider 0, 1, 2 all map to the same bucket. However, if t == 3, (0, 3) is a considered duplicates but does not map to the same bucket. This is fine since we are checking the buckets immediately before and after as well. So, as a rule of thumb, 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.

Another complication is that negative ints are allowed. A simple num / t just shrinks everything towards 0. Therefore, we can just reposition every element to start from Integer.MIN_VALUE.

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

Edits:

Actually, we can use t + 1 as the bucket size to get rid of the case when t == 0. It simplifies the code. The above code is therefore the updated version.


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

Java O(N lg K) solution

This problem requires to maintain a window of size k of the previous values that can be queried for value ranges. The best data structure to do that is Binary Search Tree. As a result maintaining the tree of size k will result in time complexity O(N lg K). In order to check if there exists any value of range abs(nums[i] - nums[j]) to simple queries can be executed both of time complexity O(lg K)

Here is the whole solution using TreeMap.

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
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length == 0 || k <= 0) {
return false;
}

final TreeSet<Integer> values = new TreeSet<>();
for (int ind = 0; ind < nums.length; ind++) {

final Integer floor = values.floor(nums[ind] + t);
final Integer ceil = values.ceiling(nums[ind] - t);
if ((floor != null && floor >= nums[ind])
|| (ceil != null && ceil <= nums[ind])) {
return true;
}

values.add(nums[ind]);
if (ind >= k) {
values.remove(nums[ind - k]);
}
}

return false;
}
}

谢谢你,可爱的朋友。