forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathContains Duplicate III.java
More file actions
119 lines (106 loc) · 4.65 KB
/
Copy pathContains Duplicate III.java
File metadata and controls
119 lines (106 loc) · 4.65 KB
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
M
1522013628
tags: BST
给一个unsorted array, 问, 是否有两个element, value相差最大为t, 而两个element的index 相差最大为k.
Note: 虽然题目名字是Contains Duplicate, 但其实要找的两个element不是duplicate, 而是Math.abs(value1 - value2) <= t.
#### TreeSet
- TreeSet还是一个set, 我们用来装已经visit过得item
- 如果window大小超过K, 那么把nums[i - k - 1] 去掉, 并且加上新的element
- 这里有个公式推算: (Math.abs(A-B) <= t) =>>>>> (-t <= A - B <= t) =>>>>>> A >= B - t, A <= B + t
- 也就是说, 如果对于 B = nums[i], 来说, 能找到一个target A, 满足上面的公式, 那么就可以 return true.
- Time O(nLogk), treeSet的大小不会超过k, 而 treeSet.ceiling(), treeSet.add(), treeSet.remove() 都是 O(logK)
- Space O(k)
#### Note
- 与Contains Duplicate II 类似概念. TreeSet有BST 因此可以直接用, 而不用自己构建BST
- 简化题目里面的重要条件 Math.abs(A-B) <= t 而推断出 A >= B - t, A <= B + t
- 并且需要需要用 TreeSet.ceiling(x): return number greater or equal to x. 这个用法要记住吧, 没别的捷径.
```
/*
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.
*/
/*
Thoughts:
Given Math.abs(A-B) <= t ->>> -t <= A - B <= t. Therefor, we want find A such as:
A >= B - t
A <= B + t
1. Need to find an element A thats greater to equal to (B-t), and also use the A needs to less or equal to (B+t)
For this, we can use a binary search tree, where to can quickly find the (B-t) and hence A.
Utilize TreeSet.ceiling() to find A
2. This binary search tree needs to be flexible in terms of removing item:
Exact same idea as in 'Contains Duplicate II': once i pass k, we need to remove any value that's in range [0, i-k) from the set, because they are out of range.
*/
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length == 0 || k <= 0 || t < 0) {
return false;
}
TreeSet<Long> treeSet = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
Long target = treeSet.ceiling((long)nums[i] - t);
if (target != null && target <= (long)nums[i] + t) {
return true;
}
if (i >= k) {
treeSet.remove((long)nums[i - k]);
}
treeSet.add((long)nums[i]);
}
return false;
}
}
/*
Incorrect: the index-based BST won't work. If item appears on both size of the tree, it's no longer possible to trace. Ex: [1, 3, 1], k=2, t=1
Also, if want to use BST, we can directly use TreeSet.
Thoughts:
1. Create binary search tree based on index, and store value/index in the node.
2. Traverse over each node of the tree, and compare the root against all children possible, to find abs(value diff) < t.
3. When abs(index diff) > k, stop diving deep.
*/
class Solution {
class Node {
int value;
int index;
Node left;
Node right;
public Node(int value, int index) {
this.value = value;
this.index = index;
}
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length == 0) {
return false;
}
final Node root = buildBinarySearchTree(nums, 0, nums.length - 1);
return findMatch(null, root, k, t);
}
private boolean findMatch(Node parent, Node node, int k, int t) {
if (node == null || (parent != null && Math.abs(parent.index - node.index) > k)) {
return false;
}
return validateDiff(node, node.left, k, t) || validateDiff(node, node.right, k, t)
|| findMatch(node, node.left, k, t) || findMatch(node, node.right, k, t);
}
private boolean validateDiff(Node nodeA, Node nodeB, int k, int t) {
if (nodeA == null || nodeB == null) {
return false;
}
return Math.abs(nodeA.value - nodeB.value) <= t && Math.abs(nodeA.index - nodeB.index) <= k;
}
private Node buildBinarySearchTree(int[] nums, int start, int end) {
if (start > end || start < 0 || end >= nums.length ) {
return null;
}
if (start == end) {
return new Node(nums[start], start);
}
int mid = start + (end - start) / 2;
Node node = new Node(nums[mid], mid);
node.left = buildBinarySearchTree(nums, start, mid - 1);
node.right = buildBinarySearchTree(nums, mid + 1, end);
return node;
}
}
```