Java O(nlog(n)) solution using TreeSet


  • 0
    Q
    public class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (nums == null || nums.length<=1 || k==0){
                return false;
            }
            Comparator<Number> c1 = new Comparator<Number>(){
                public int compare(Number n1, Number n2){
                   return new Long(n1.val).compareTo(new Long(n2.val));
               }
           };
           TreeSet<Number> set = new TreeSet<Number>(c1);
           LinkedList<Number> l = new LinkedList<Number>();
           for (int i=0;i<nums.length;i++){
        	   if (l.size()>k){
        		   Number toRemove = l.pollFirst();
        		   set.remove(toRemove);
        	   }
        	   
        	   Number n = new Number();
               n.val = nums[i];
               n.index = i;
             
               if (set.isEmpty() == false){
            	   java.util.NavigableSet<Number> s1 = set.tailSet(n, true);
    	           if (s1.isEmpty() == false && s1.first().val - n.val <= t){
    	        	   return true;
    	           }
    	           
    	           java.util.NavigableSet<Number> s2 = set.headSet(n, true);
    	           if (s2.isEmpty() == false && n.val - s2.last().val <= t){
    	        	   return true;
    	           }
               }
               l.add(n);
               set.add(n);
           }
           
           
           return false;
        }
        
        class Number{
            long val;
            int index;
        }
    }

  • 0
    M
    This post is deleted!

  • 0
    K

    The set will not contain the same number twice. The set is a window of size k. Before a duplicate is added, it is checked if there is a close number in that set. If so, it will return true. Did this answer your question?


  • 0
    K

    Do you need a Number class? Is it alright to just store the value without the index in the TreeSet?


  • 0
    M

    Exactly, thank you. Really set will be enough.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.