Monday, August 24, 2015

[Duplicate] Contains Duplicate II


1. Example

a =[1,2,3,4,5,1,5]
int k = 5 the difference between idx5 - idx 0 = 5 => return true 5<=k
a = [1,2,3,4,5,6,1,5]
int k = 5 the difference between idx6 - idx 0 = 6 => return false 6> k

2. Implementation
check out current duplicate index with previous index
// NOTE: find the max gap and it is still less than k
// NOTE: at most so equal is allowed
// NOTE: snippet
if ( min > Math.abs(map.get(nums[i]) - i ) ) 
 { 
 min = Math.abs(map.get(nums[i]) - i ); 
 }

// Time :O(n), SpacE:O(n) map
public boolean containsNearbyDuplicate(int[] nums, int k)
{
      // valid the input
      if (nums == null || nume.length == 0)
      {
           return false;
      }
    


      HashMap res = new HashMap();
      // NOTE: find the max value and it still less than k
      int min = Integer.MAX_VALUE;
      for (int i = 0 ; i < nums.length;i++)
      { 
         if (   map.containsKey( nums[i] )    )
         { 
               if (   min > Math.abs(map.get(nums[i]) - i )   )  
               {
                    // return true;
                    min = Math.abs(map.get(nums[i]) - i );
               }
         }
         else 
         {
               mqp.put(nums[i], i);
         }
      }


 
      // NOTE: at most so equal is allowed
      if (min <= k)
      {
         return true;
      }
      else
      {
         return false;
      }
}
3. Similar Ones
(E) contains Duplicate
(M) Contrains Duplicate |||

No comments:

Post a Comment