Dada una matriz de enteros, averigüe si hay dos índices distintos i y j en la matriz de modo que la diferencia entre nums[i] y nums[j] es como máximo t y la diferencia entre i y j es como máximo k.
Solución Java 1 – Simple
Esta solución simple. Su complejidad de tiempo es O (nlog (k)).
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if(nums==null||nums.length<2||k<0||t<0) return false; TreeSet<Long> set = new TreeSet<Long>(); for(int i=0; i<nums.length; i++){ long curr = (long) nums[i]; long leftBoundary = (long) curr-t; long rightBoundary = (long) curr+t+1; //right boundary is exclusive, so +1 SortedSet<Long> sub = set.subSet(leftBoundary, rightBoundary); if(sub.size()>0) return true; set.add(curr); if(i>=k){ // or if(set.size()>=k+1) set.remove((long)nums[i-k]); } } return false; } |
Solución Java 2: obsoleta
El método floor (x) devuelve el mayor valor que es menor que x. Los métodos de techo (x) devuelven el valor mínimo que es mayor que x. Lo siguiente es un ejemplo.
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if (k < 1 || t < 0) return false; TreeSet<Integer> set = new TreeSet<Integer>(); for (int i = 0; i < nums.length; i++) { int c = nums[i]; if ((set.floor(c) != null && c <= set.floor(c) + t) || (set.ceiling(c) != null && c >= set.ceiling(c) -t)) return true; set.add(c); if (i >= k) set.remove(nums[i - k]); } return false; } |
