Java treeset implementation NlogK


  • 13
    T

    this is a very good demonstration of the use of TreeSet ---- which we rarely use normally.

        public class Solution {
    
        public boolean containsNearbyAlmostDuplicate(final int[] nums, int kk, long t) {
            if (nums.length < 2) return false;
            if (kk == 0) return false;
            TreeSet<Long> window = new TreeSet<Long>();
            
            for(int i=0;i<nums.length;i++) {
    
                // check dup, window size <= kk right now
            	if ( window.floor(nums[i] + t) !=null && window.floor(nums[i]+t) >= nums[i]-t ) return true;
            	
                window.add(new Long(nums[i]));
                
                
                if (i >= kk) {
                    //remove one, the size has to be kk on the next fresh step
                	window.remove(new Long(nums[i-kk]));
                }
            }
            
            return false;
        }
    }

  • 0
    L

    why TreeSet<Integer> doesn't have the floor() method?


  • 0

    Could you please tell me why it's faster when treeset's elements are Long instead of Integer?


  • 1
    A

    I don't think it has to do with performance. It's possible that nums[i] + t > Integer.MAX_VALUE.
    Nice solution!


  • 0
    R

    How is this nlogk? Isnt this supposed to be nlogn which is the cost of constructing the tree set?


  • 1
    R

    nlogk since his treeSet's size is k


  • 0

    @liji94188 you need to declare it in this way :
    TreeSet<Integer> set = new TreeSet<>();


Log in to reply
 

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