LeetCode 219 - Contains Duplicate II
LeetCode 217 - Contains Duplicate
LeetCode 220 - Contains Duplicate III
LeetCode 220 - Contains Duplicate III | 书影博客
Output: false
X. Bucket Sort O(n)
https://baihuqian.github.io/2018-07-06-contains-duplicate-iii/
https://zhuhan0.blogspot.com/2017/06/leetcode-220-contains-duplicate-iii.html
https://leetcode.com/problems/contains-duplicate-iii/discuss/61645/AC-O(N)-solution-in-Java-using-buckets-with-explanation
The naive solution is to maintain a sliding window with size k, when we add an element nums[i], compare the nums[i] with each element in the window. If it is less or equal to t, return true. We return true because the distance between i and each element in the window must be less or equal to k. The complexity of this solution would be O(nk).
We could use a treeSet to improve the complexity. The treeSet is essentially a balanced binary search tree. We put k elements in the treeSet, which is a sliding window. So when we insert an element to the treeSet, we need to remove one from the end.
So the basic idea is for each element nums[i], we check if there is any element between [nums[i] - t, nums[i] + t]. If yes, return true.
//TIME COMPLEXITY
treeset.subset
O(n logk)
解法II：“滑动窗口” + TreeSetTreeSet数据结构（Java）使用红黑树实现，是平衡二叉树的一种。
该数据结构支持如下操作：
http://blog.csdn.net/xudli/article/details/46323247
这题主要考察的是两个元素之间的关系。维持一个长度为k的window, 每次检查新的值是否与原来窗口中的所有值的差值有小于等于t的. 如果用两个for循环会超时O(nk). 使用treeset( backed by binary search tree) 的subSet函数,可以快速搜索. 复杂度为 O(n logk)
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if(k<1 || t<0 || nums==null) return false; SortedSet<Long> set = new TreeSet<Long>(); for(int j=0; j<nums.length; j++) { // the previous solution is better. SortedSet<Long> subSet = set.subSet((long)nums[j]-t, (long)nums[j]+t+1); if(!subSet.isEmpty()) return true; if(j>=k) { set.remove((long)nums[j-k]); } set.add((long)nums[j]); } return false; }
Consider overflow:
http://www.tangjikai.com/algorithms/leetcode-217-contains-duplicate
https://codesolutiony.wordpress.com/2015/06/01/leetcode-contains-duplicate-iii/
No need to use Hashmap, only the key is used.
http://leetcode.tgic.me/contains-duplicate-iii/index.html: good idea to create a new data strcuture to wrap the logic, but the time complexity is still O(nlogk).
http://blog.csdn.net/xudli/article/details/46236267
Given an array of integers and an integer k, return true if and only if there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
This seems not right, when map.containsKey(nums[i]), it's not put into the map.
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
http://waltertan12.github.io/blog/whiteboarding/2016/01/22/contains-duplicate-iii.html
var len = nums.length, i, j, num;
for (i = 0; i < len; i++) {
num = nums[i];
// Check each value in the window for a match to num
for (j = 1; j <= k; j++) {
if (Math.abs(nums[i + j] - num) <= t) return true;
}
}
return false;
X. Sort
http://yucoding.blogspot.com/2015/10/leetcode-question-contains-duplicate-iii.html
At the first glance, it is natural to think that "using two loops to search every two elements within distance k" to solve this problem. However, the O(n^2) time complexity is not accepted for OJ.
Here is how I think of the problem, since it is asking for whether two indices exists ... , we have to search the array in some way. There are two constrains: one is related to element values in the array, the other is related to indices. So, we have to consider the two at the same time when checking one pair of elements. In other words, we have to know the element value and the element index at the same, and using some strategy, to scan the array and find if there is any pair satisfy the constrains.
Let's take an example, say the array is A = [3,6,0,4], and we set t = 2, k =2.
Let's sort the array according to the value,
the values of the array becomes: A' = [0, 3, 4, 6]
the indices of the array becomes: I' = [2, 0, 3, 1]
We rewrite them into one array:
P = [(0,2), (3,0), (4,3), (6,1)]
Now we are searching the pairs, starting from the first pair:
(0, 2) where 0 is the value 2 is the index.
Now we have pair P[i] = (0,2), i = 0, we need P[j] to check if P[i] and P[j] satisfy the constrains that
abs(P[i][0] - P[j][0]) < = t and abs(P[i][1] - P[j][1]) < = k.
When compare current pair P[0] = (0,2) and next pair P[1] = (3,0), abs(0-3) > t. It seems natural to keep the first pair P[0] and search the rest of array after P[1], but in fact it is not an efficient way, especially when k is a large number.
Since we have already sorted the array, if the value difference between P[0] and P[1] is greater than t, the value difference between P[0] and P[2], P[3] ... P[end] must also greater than t. If current comparison is not satisfied, all the other comparisons are not even necessary. We can move P[0] to next element.
While on the other hand, if the value difference <= t, but the index difference > k, we still have to keep the current P[i] and move P[j] until meets the above scenario or the end of the array.
In this example:
1. Compare (0,2) and (3,0), abs(0-3) >t
2. Compare (3,0) and (4,3), abs(3-4) <=t , abs(0-3) > k
3. Compare (3,0) and (6,1), abs(6-3) > t
4..Compare (4,3) and (6,1), abs(4-6) <=t, abs(3-1)<=k, satisfied. Return True.
X. LeetCode 219 - Contains Duplicate II
http://shibaili.blogspot.com/2015/06/day-111-contains-duplicate-ii.html
方法1，bucket sort，O(n)，如果每个bucket里出现2个元素，则可直接返回true。所以确保了在程序运行过程中每个bucket只可能存在1个或者0个元素
casting的问题
k < 1 或 t < 0 直接返回false
(long long)t + 1, + 1是为了防止当t 为0
Read full article from [LeetCode]Contains Duplicate III | 书影博客
LeetCode 217 - Contains Duplicate
LeetCode 220 - Contains Duplicate III
LeetCode 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 absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2 Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
X. Bucket Sort O(n)
https://baihuqian.github.io/2018-07-06-contains-duplicate-iii/
Inspired by bucket sort, we can achieve linear time complexity in our problem using buckets as window.
Bucket sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, using a different sorting algorithm. For example, we have 8 unsorted integers, 20, 13, 4, 49, 41, 32, 9, 18. We create 5 buckets covering the inclusive ranges of [0,9], [10,19], [20, 29], [30, 39], [40, 49] individually. Each of the eight elements is in a particular bucket. For element with value x, its bucket label is
x / w and here we have w = 10. Sort each bucket using some other sorting algorithm and then collect all of them bucket by bucket.
Back to our problem, the critical issue we are trying to solve is: For a given element x is there an item in the window that is within the range of
[x-t, x+t]?
Could we do this in constant time?
Let us consider an example where each element is a person’s birthday. Your birthday, say some day in March, is the new element
x. Suppose that each month has 30 days and you want to know if anyone has a birthday within t = 30 days of yours. Immediately, we can rule out all other months except February, March, April.
The reason we know this is because each birthday belongs to a bucket we called month! And the range covered by the buckets are the same as distance t which simplifies things a lot. Any two elements that are not in the same or adjacent buckets must have a distance greater than t.
We apply the above bucketing principle and design buckets covering the ranges of
..., [0,t], [t+1, 2t+1], ......,[0,t],[t+1,2t+1],.... We keep the window using this buckets. Then, each time, all we need to check is the bucket that x belongs to and its two adjacent buckets. Thus, we have a constant time algorithm for searching almost duplicate in the window.
One thing worth mentioning is the difference from bucket sort – Each of our buckets contains at most one element at any time, because two elements in a bucket means “almost duplicate” and we can return early from the function. Therefore, a HashMap with an element associated with a bucket label is enough for our purpose.
https://segmentfault.com/a/1190000009496516题意找到一组数，nums[i] and nums[j] 他们idx差值在k以内， 即 j - i <= k.
他们的差的绝对值在t以内，即 Math.abs(nums[i] - nums[j]) <= t.
我们可以构建一个大小为t+1的bucket, 比如[0, 1, 2, 3, ... , t] 最大绝对值差的两个数就是t和0.
如果两个数字出现在同一个Bucket内，说明我们已经找到了。 如果不是，则在相邻的两个bucket内再找。
如果相邻的bucket内元素绝对值只差在t以内，说明我们知道到了，返回true.
为了保证j - i <= k，我们在i>=k时，删除 nums[i-k]对应的Bucket.
假定把数组元素分到多个桶中，这里桶需要设置为合理的大小。使得相差t的元素一定会映射到同一个桶或者相邻的桶中。
例如，桶的大小是3，这样0，1，2就映射到同一个桶中。
当t=3时，0和3被视作重复元素，但他们处于相邻的桶中。
当t=3时，0和3被视作重复元素，但他们处于相邻的桶中。
因此，我们需要设置合理的桶的大小 ，通常设置为t或者t+1。这里我们设置为t+1，以避免考虑t=0的情况。(注意：t=0时，该问题退化为Contains Duplicate II)这样每个元素就被映射到第n/(t+1)个桶中。
这样，判断两个元素大小相差t的话，我们仅需要考虑以下两种情况：
- 这两个元素是否在同一个桶中
- 这两个元素是否在相邻桶中，且大小相差小于等于t
思想是以t+1为间隔来分桶，对于一个数，将其分到第key = num / (t + 1) 个桶中，我们只需要查找相同的和相邻的桶的元素就可以判断有无重复。
比如t = 4，那么0~4为桶0，5~9为桶1，10~14为桶2 。
使用t+1个桶是为啥？这是为了避免除以0的错误，可能t = 0.
下面，C++和Java的版本，如果num为负数，那么key -= 1，因为比C++/Java 的负数取整是：-2 /3 = 0，这题这样是不行的。
而Python则OK, -2 // 3 = -1。
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(k <= 0 || t < 0) return false;
HashMap<Long, Long> keyToNum = new HashMap<>();
long div = (long)t + 1;
for (int i = 0; i < nums.length; i++) {
long num = (long)nums[i];
long key = num / div;
if(num < 0) key--;
if (keyToNum.containsKey(key)
|| keyToNum.containsKey(key + 1) && keyToNum.get(key + 1) - num <= t
|| keyToNum.containsKey(key - 1) && num - keyToNum.get(key - 1) <= t)
return true;
if (i >= k) keyToNum.remove(((long)nums[i - k]) / div);
keyToNum.put(key, num);
}
return false;
}
- Divide numbers into buckets of size t + 1. For example, numbers between 0 and t are in bucket 0, and numbers between t + 1 and 2t + 1 are in bucket 1.
- Iterate through the array. Use a hash map to store bucket -> number mappings. Maintain a window of size k, i.e. there are at most k mappings in the map.
- This gives me three cases as I iterate:
- Map contains the same bucket: return true, because I know the numbers satisfy both requirements.
- Neighboring buckets contain a number whose difference with the current number <= t: return true.
- If neither of 1 and 2 happens, put the mapping of current bucket -> number into the map. If current index is larger than k, evict the mapping of the bucket of array[index - k]. It is safe to remove this mapping because its index will never be within k difference with a future number.
Note: there may be three cases of integer overflow:
- Bucket size: if t = Integer.MAX_VALUE.
- Neighboring buckets: if t = 0, then size of bucket = 1. If there is Integer.MAX_VALUE in the array, its neighbor bucket will overflow.
- Difference between numbers.
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.
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;
}
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) the two in the same bucket
(2) the two in neighbor bucketsprivate 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;
}The naive solution is to maintain a sliding window with size k, when we add an element nums[i], compare the nums[i] with each element in the window. If it is less or equal to t, return true. We return true because the distance between i and each element in the window must be less or equal to k. The complexity of this solution would be O(nk).
We could use a treeSet to improve the complexity. The treeSet is essentially a balanced binary search tree. We put k elements in the treeSet, which is a sliding window. So when we insert an element to the treeSet, we need to remove one from the end.
So the basic idea is for each element nums[i], we check if there is any element between [nums[i] - t, nums[i] + t]. If yes, return true.
//TIME COMPLEXITY
treeset.subset
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
TreeMap
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
return new AscendingSubMap<>(this,
false, fromKey, fromInclusive,
false, toKey, toInclusive);
}
X. TreeSet/TreeMap - nlogk
https://www.liuchuo.net/archives/3150
https://leetcode.com/problems/contains-duplicate-iii/discuss/61655/Java-O(N-lg-K)-solution
http://www.programcreek.com/2014/06/leetcode-contains-duplicate-iii-java/X. TreeSet/TreeMap - nlogk
https://www.liuchuo.net/archives/3150
分析：建立一个map，对应的是元素的值到元素的下标的映射。指针i将nums数组从头遍历到尾，j指针一开始指向0。i向右走的时候如果i和j之差大于k，且m中有nums[j]，就将nums[j]从m中移除，且j向前走一步～这样就保证了m中所有的元素满足第一个条件：i和j的差的绝对值不超过k～
接下来考虑nums[i]和nums[j]的差的绝对值不超过t，abs(num[i] – nums[j]) <= t 则 nums[j]的最小可能满足条件的值为>=nums[i] – t的，所以使用map中的lower_bound，寻找第一个大于等于nums[i] – t的地方，找到后标记为a，此时的a只是取到了可能满足的最小的a，但(a – nums[i])不一定满足，所以检验a是否存在于map中且是否abs(a->first – nums[i]) <= t。如果都满足说明可以return true～
为什么要循环的最后写map的插入呢，因为比较的是i之前的所有元素～为了防止找到的是nums[i]本身，然后让nums[i]自己本身和自己比较差值了，这样结果就不对了～
如果到最后都没有能够return true，则return false～
http://www.cnblogs.com/grandyang/p/4545261.html如果到最后都没有能够return true，则return false～
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { map<long long, int> m; int j = 0; for (int i = 0; i < nums.size(); ++i) { if (i - j > k) m.erase(nums[j++]); auto a = m.lower_bound((long long)nums[i] - t); if (a != m.end() && abs(a->first - nums[i]) <= t) return true; m[nums[i]] = i; } return false; }
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)
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;
} public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if (nums == null || nums.length == 0 || k < 0 || t < 0) { return false; } SortedSet<Long> set = new TreeSet<>(); for (int i = 0; i < nums.length; i++) { long lower = (long) nums[i] - t; long upper = (long) nums[i] + t + 1; // use long to avoid overflow, e..g. nums[i] and t is Integer.MAX_VALUE SortedSet<Long> boundary = set.subSet(lower, upper); if (!boundary.isEmpty()) { return true; } set.add((long) nums[i]); if (i >= k) { set.remove((long) nums[i - k]); } } return false; }解法II：“滑动窗口” + TreeSetTreeSet数据结构（Java）使用红黑树实现，是平衡二叉树的一种。
该数据结构支持如下操作：
1. floor()方法返set中≤给定元素的最大元素；如果不存在这样的元素，则返回 null。
2. ceiling()方法返回set中≥给定元素的最小元素；如果不存在这样的元素，则返回 null。
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(k < 1 || t < 0)
return false;
TreeSet<Integer> set = new TreeSet<>();
for(int i = 0; i < nums.length; i++){
int n = nums[i]; // Use variable floor = set.floor(n)
if(set.floor(n) != null && n <= t + set.floor(n) ||
set.ceiling(n) != null && set.ceiling(n) <= t + n)
return true;
set.add(n);
if (i >= k)
set.remove(nums[i - k]);
}
return false;
}http://blog.csdn.net/xudli/article/details/46323247
这题主要考察的是两个元素之间的关系。维持一个长度为k的window, 每次检查新的值是否与原来窗口中的所有值的差值有小于等于t的. 如果用两个for循环会超时O(nk). 使用treeset( backed by binary search tree) 的subSet函数,可以快速搜索. 复杂度为 O(n logk)
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if(k<1 || t<0 || nums==null) return false; SortedSet<Long> set = new TreeSet<Long>(); for(int j=0; j<nums.length; j++) { // the previous solution is better. SortedSet<Long> subSet = set.subSet((long)nums[j]-t, (long)nums[j]+t+1); if(!subSet.isEmpty()) return true; if(j>=k) { set.remove((long)nums[j-k]); } set.add((long)nums[j]); } return false; }
Consider overflow:
http://www.tangjikai.com/algorithms/leetcode-217-contains-duplicate
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {TreeSet treeset = new TreeSet<>();for (int i = 0; i < nums.length; ++i) {Integer floor = nums[i] - t;Integer ceiling = nums[i] + t + 1;if ((long) nums[i] - (long) (t) < Integer.MIN_VALUE) floor = Integer.MIN_VALUE;if ((long) nums[i] + (long) (t) > Integer.MAX_VALUE - 1) ceiling = Integer.MAX_VALUE;if (t >= 0 && treeset.subSet(floor, ceiling).size() != 0) return true;treeset.add(nums[i]);if (i >= k) treeset.remove(nums[i - k]);}return false;}
解法I：“滑动窗口” + 字典（桶）
其中式b是式c的充分非必要条件，因为逆否命题与原命题等价，所以：
因此只需要维护一个大小为k的窗口（字典）numDict，其中键为nums[i] / t，值为nums[i]。
遍历数组nums时，检查nums[i]与键集
https://www.jianshu.com/p/45d7c879f4bf{floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1}对应的值的差值即可。
顺序扫描数组，每次仅保存size=k的滑动窗口，并用TreeSet或bucket存储窗口中现有的元素，加入新元素后判断是否与集合中元素满足difference<=t的条件。注意窗口的更新，如何维护treeset或bucket（加入新元素的同时，删除最早加入的元素）。
这里要注意为什么需要使用treeset与bucket，而不是queue？原因是treeset和bucket具有根据input value快速查找的能力，若新加入的元素为nums[i]，
则treeset可以通过floor与ceiling在O(log k)的时间复杂度下查找最相近的元素。
这里要注意为什么需要使用treeset与bucket，而不是queue？原因是treeset和bucket具有根据input value快速查找的能力，若新加入的元素为nums[i]，
则treeset可以通过floor与ceiling在O(log k)的时间复杂度下查找最相近的元素。
Long floor = set.floor((long) nums[i]);
Long ceiling = set.ceiling((long) nums[i]);
No need to use Hashmap, only the key is used.
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if (nums == null) { return false; } TreeMap<Long, Integer> map = new TreeMap<Long, Integer>();//pair: value-index for (int i = 0; i < nums.length; i++) { if (i > k) { map.remove((long)nums[i-k-1]); } long val = (long)nums[i]; Long greater = map.ceilingKey(val); if (greater != null && greater - val <= t) { return true; } Long smaller = map.lowerKey(val); if (smaller != null && val - smaller <= t) { return true; } map.put(val, i); } return false; }http://leetcode.tgic.me/contains-duplicate-iii/index.html: good idea to create a new data strcuture to wrap the logic, but the time complexity is still O(nlogk).
http://blog.csdn.net/xudli/article/details/46236267
Given an array of integers and an integer k, return true if and only if there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
This seems not right, when map.containsKey(nums[i]), it's not put into the map.
public boolean containsNearbyDuplicate(int[] nums, int k) {
if(nums==null || nums.length<2) return false;
//key=int, val=index
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0; i<nums.length; i++) {
if(map.containsKey(nums[i])) {
int j = map.get(nums[i]);
if(i-j<=k) return true;
} else {
map.put(nums[i], i);
}
}
return false;
}
http://www.programcreek.com/2014/05/leetcode-contains-duplicate-ii-java/public boolean containsNearbyDuplicate(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i=0; i<nums.length; i++){ if(map.containsKey(nums[i])){ int pre = map.get(nums[i]); if(i-pre<=k) return true; } map.put(nums[i], i); } return false; } |
public boolean containsDuplicate(int[] nums) { if(nums==null || nums.length==0) return false; HashSet<Integer> set = new HashSet<Integer>(); for(int i: nums){ if(!set.add(i)){ return true; } } return false; }
http://waltertan12.github.io/blog/whiteboarding/2016/01/22/contains-duplicate-iii.html
This approach results in a time complexity of O(n * k) because each element requires a O(k)search. In the worst case, k could be set equal n making this algorithm O(n ** 2).
An important takeaway from this approach is that we are scanning from a window from i to i + kand checking to see if we have a matching value for nums[i]. To be more exact, we are looking for a value
Math.abs(nums[i + k] - nums[i]) <= t
You can think of this window as an array that holds all the values in that range; and, as we iterate through the array, we unshift the value at i and push in the value at i + k + 1.
var containsNearbyAlmostDuplicate = function (nums, k, t) {var len = nums.length, i, j, num;
for (i = 0; i < len; i++) {
num = nums[i];
// Check each value in the window for a match to num
for (j = 1; j <= k; j++) {
if (Math.abs(nums[i + j] - num) <= t) return true;
}
}
return false;
X. Sort
http://yucoding.blogspot.com/2015/10/leetcode-question-contains-duplicate-iii.html
At the first glance, it is natural to think that "using two loops to search every two elements within distance k" to solve this problem. However, the O(n^2) time complexity is not accepted for OJ.
Here is how I think of the problem, since it is asking for whether two indices exists ... , we have to search the array in some way. There are two constrains: one is related to element values in the array, the other is related to indices. So, we have to consider the two at the same time when checking one pair of elements. In other words, we have to know the element value and the element index at the same, and using some strategy, to scan the array and find if there is any pair satisfy the constrains.
Let's take an example, say the array is A = [3,6,0,4], and we set t = 2, k =2.
Let's sort the array according to the value,
the values of the array becomes: A' = [0, 3, 4, 6]
the indices of the array becomes: I' = [2, 0, 3, 1]
We rewrite them into one array:
P = [(0,2), (3,0), (4,3), (6,1)]
Now we are searching the pairs, starting from the first pair:
(0, 2) where 0 is the value 2 is the index.
Now we have pair P[i] = (0,2), i = 0, we need P[j] to check if P[i] and P[j] satisfy the constrains that
abs(P[i][0] - P[j][0]) < = t and abs(P[i][1] - P[j][1]) < = k.
When compare current pair P[0] = (0,2) and next pair P[1] = (3,0), abs(0-3) > t. It seems natural to keep the first pair P[0] and search the rest of array after P[1], but in fact it is not an efficient way, especially when k is a large number.
Since we have already sorted the array, if the value difference between P[0] and P[1] is greater than t, the value difference between P[0] and P[2], P[3] ... P[end] must also greater than t. If current comparison is not satisfied, all the other comparisons are not even necessary. We can move P[0] to next element.
While on the other hand, if the value difference <= t, but the index difference > k, we still have to keep the current P[i] and move P[j] until meets the above scenario or the end of the array.
In this example:
1. Compare (0,2) and (3,0), abs(0-3) >t
2. Compare (3,0) and (4,3), abs(3-4) <=t , abs(0-3) > k
3. Compare (3,0) and (6,1), abs(6-3) > t
4..Compare (4,3) and (6,1), abs(4-6) <=t, abs(3-1)<=k, satisfied. Return True.
思路一：naive thinking
考虑排序，但排序时也得带上index，即需要记录排序前各个元素原先的下标。排序后，check数组中是否存在符合at most t & at most k的元素。
https://leetcode.com/problems/contains-duplicate-iii/discuss/61734/AC-Java-solution-without-set-or-dictionary.-Sort-the-nums-and-record-the-positions考虑排序，但排序时也得带上index，即需要记录排序前各个元素原先的下标。排序后，check数组中是否存在符合at most t & at most k的元素。
we couldn't say this to be O(n^2), it's proper to say this to be O(tn) for the nested for loops and O(nlgn) for the sort process
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(nums.length<2||k<1||t<0) return false;
ValuePosPair[] valPosArr = new ValuePosPair[nums.length];
for(int i =0;i<nums.length;i++) valPosArr[i] = new ValuePosPair(nums[i],i);
Arrays.sort(valPosArr);
for(int i=0;i<valPosArr.length;i++){
for(int j=i+1;j<valPosArr.length&&((long)valPosArr[j].val-(long)valPosArr[i].val<=(long)t);j++){
if(Math.abs(valPosArr[j].pos-valPosArr[i].pos)<=k) return true;
}
}
return false;
} class ValuePosPair implements Comparable<ValuePosPair>{
int val;
int pos;
ValuePosPair(int v, int p) { val = v; pos = p;}
} static bool pcomp(pair<int,int> a, pair<int,int> b) { return a.first < b.first ; } bool search(vector<pair<int,int> > l, int t, int k){ int po = 0; while (po < l.size()){ int i = po + 1; while (i < l.size()){ if ((abs(long(l[i].first) - long(l[po].first)) <= t)&&(abs(l[i].second - l[po].second)<= k)){ return true; }else{ if (abs(long(l[i].first) - long(l[po].first)) > t){ break; }else{ i+=1; } } } po += 1; } return false; } bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { if (nums.size() == 0 ){ return false; } vector<pair<int,int> > pp; for (int i=0;i<nums.size();i++){ pp.push_back(make_pair(nums[i], i)); } sort(pp.begin(),pp.end(),pcomp); return search(pp, t, k); }http://shibaili.blogspot.com/2015/06/day-111-contains-duplicate-ii.html
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
casting的问题
k < 1 或 t < 0 直接返回false
(long long)t + 1, + 1是为了防止当t 为0
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { if (k <= 0 || t < 0) return false; unordered_map<long long,int> bucket; for (int i = 0; i < nums.size(); i++) { long long inter = nums[i] + 2147483648; long long curBucket = inter / ((long long)t + 1); if (bucket.find(curBucket) != bucket.end() || (bucket.find(curBucket - 1) != bucket.end() && abs((long long)nums[i] - bucket[curBucket - 1]) <= t) || (bucket.find(curBucket + 1) != bucket.end() && abs((long long)nums[i] - bucket[curBucket + 1]) <= t)) { return true; } bucket[curBucket] = (long long)nums[i]; if (i - k >= 0) { long long oldBucket = (nums[i - k] + 2147483648) / ((long long)t + 1); bucket.erase(oldBucket); } } return false; }