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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
// 220. Contains Duplicate III
#include "leetcode.h"
/*
* given an integer array 'nums' and two integers 'index_diff'
* and 'value_diff'. find a pai of indices '(i, j)' such that:
* i != j
* abs(i - j) <= index_diff
* abs(num[i] - num[j]) <= value_diff
* return true if such pair exists or false otherwise
*/
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int> &nums, int index_diff,
int value_diff) {
int n = nums.size();
if (n == 0 || index_diff < 0 || value_diff < 0)
return false;
unordered_map<int, int> buckets;
for (int i = 0; i < n; i++) {
int b = nums[i] / ((long)value_diff + 1);
if (nums[i] < 0)
--b;
if (buckets.find(b) != buckets.end())
return true;
else {
buckets[b] = nums[i];
if (buckets.find(b - 1) != buckets.end() &&
(long)nums[i] - buckets[b - 1] <= value_diff)
return true;
if (buckets.find(b + 1) != buckets.end() &&
(long)buckets[b + 1] - nums[i] <= value_diff)
return true;
if (buckets.size() > index_diff) {
int remove = nums[i - index_diff] / ((long)value_diff + 1);
if (nums[i - index_diff] < 0)
--remove;
buckets.erase(remove);
}
}
}
return false;
}
};
int main() {
Solution obj;
vector<int> n1 = {1, 2, 3, 1}, n2 = {1, 5, 9, 1, 5, 9};
printf("%d\n", obj.containsNearbyAlmostDuplicate(n1, 3, 0)); // expect: 1
printf("%d\n", obj.containsNearbyAlmostDuplicate(n2, 2, 3)); // expect: 0
}
|