I finally got AC in java with the coherent code


  • 3
    Y

    First,let's start with simple and instuitive method which is two loop ,one for enumerating the nums[i] ,the other one for enumerating the nums[j] ,j-i<=k;

    Pseudo code:
                            for(int i=0;i<nums.length-1;i++)
                                     for(int j=1;j<=k;j++) //becaust the problem indicate the distinct i and j,so j start from 1
                                             see if there exist the difference bettween nums[i] and nums[j+i]
                                              is at most t;
    

    this method is timeout with no doubt,how can we improve it?.if we notice in the second loop that everytime i++, we will take o(n) time make comparison,but the number used to compare actually change one.so if we use a good data structure store it,everytime we will just take o(logN) to compare and O(logN) to change one number in this data structure.most People use set data structure to store it.you can choose the others.

    Pseudo code:
                           for(int i=0;i<nums.length-1;i++)
                                     see if there exist the difference bettween nums[i] and the number
                                                      in the set is at most t.               
    

    finally ,if you want the AC,you must take care some boundary problems. the following is my AC code which is not perfect ,just for refer.

     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t){
    	 TreeSet<Integer> set = new TreeSet<Integer>();
    	 if(nums.length==0 || k==0)
    		 return false;
    	 k=k<nums.length-1?k:nums.length-1;
    	 for(int i=1;i<=k;i++)
    		 set.add(nums[i]);
    	 for(int i=0;i<nums.length-1;i++){
    		 if(nums[i]-t-1>=nums[i]+t)
    			 return false;
    		 if(!set.subSet(nums[i]-t, nums[i]+t).isEmpty()||set.contains(nums[i]+t))		 
    			 return true;				 
    		 else{
    			 if(i!=nums.length-2)
    				 set.remove(nums[i+1]);
    			 else
    				 break;
    			 if(i+k+1 <nums.length)
    				 set.add(nums[i+k+1]);
    		 }
    	 }
    	 return false;
     }

  • 2
    L

    if(nums[i]-t-1>=nums[i]+t)
    return false;
    What's this weird code for?


Log in to reply
 

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