My solution using BST. Remove elements may improve the efficiency


  • 0
    X

    Remove the elements that its distance from the current index is larger than k.
    And then check if the BST contains value within [nums[i]-t,nums[i]+t]

    class TreeNode
    {
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        
        public TreeNode(TreeNode parent,int value)
        {
            this.value=value;
            this.parent=parent;
        }
    }
    
    class BST
    {
        TreeNode root=null;
        public BST()
        {
            
        }
        
        public boolean insert(int x)
        {
            if(root==null)
            {
                root=new TreeNode(null,x);
            }
            else
            {
                TreeNode parent=root,cur=root;
                while(cur!=null)
                {
                    if(x==cur.value)
                    {
                        break;
                    }
                    else if(x<cur.value)
                    {
                        parent=cur;
                        cur=cur.left;
                        if(cur==null)
                            parent.left=new TreeNode(parent,x);
                    }
                    else
                    {
                        parent=cur;
                        cur=cur.right;
                        if(cur==null)
                            parent.right=new TreeNode(parent,x);
                    }
                }
                
            }
            return true;
        }
        
        public TreeNode find(int x)
        {
                TreeNode cur=root;
                while(cur!=null)
                {
                    if(x==cur.value)
                    {
                        return cur;
                    }
                    else if(x<cur.value)
                    {
                        cur=cur.left;
                    }
                    else
                    {
                        cur=cur.right;
                    }
                }
                return cur;
        }
        
        public void remove(int x)
        {
            TreeNode node=find(x);
            TreeNode y=null;
            if(node.left==null||node.right==null)
                y=node;
            else
                y=successor(node);
            TreeNode child=null;
            if(y.left!=null)
            {
                child=y.left;
            }
            else
            {
                child=y.right;
            }
            if(child!=null)
            {
                child.parent=y.parent;
            }
            
            if(y==root)
            {
                root=child;
            }
            else
            {
                if(y==y.parent.left)
                {
                    y.parent.left=child;
                }
                else
                {
                    y.parent.right=child;
                }
            }
            
            if(y!=node)
            {
                node.value=y.value;
            }
            
            return ;
            
        }
        
        private TreeNode successor(TreeNode node) {
    
        	if(node.right!=null)
        	{
        		TreeNode cur=node.right;
        		while(cur.left!=null)
        			cur=cur.left;
        		return cur;
        	}
        	else
        	{
        		TreeNode p=node.parent;
        		while(p!=null&&node==p.right)
        		{
        			node=p;
        			p=p.parent;
        		}
        		return p;
        	}
    	}
    
    	public boolean containsInRange(int s,int e)
        {
            TreeNode cur=root;
            while(cur!=null)
            {
            	
                if(cur.value>=s&&cur.value<=e)
                {
                    return true;
                }
                else if(cur.value>e)
                {
                    cur=cur.left;
                }
                else
                {
                	cur=cur.right;
                }
            }
            return false;
        }
        
        
    }
    
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums==null||nums.length==0)
            return false;
        if(t<0)
        	return false;
        BST bst=new BST();
        
        for(int i=0;i<nums.length;i++)
        {
            if(i>k)
            {
                bst.remove(nums[i-k-1]);
            }
            int low=nums[i]>Integer.MIN_VALUE+t?nums[i]-t:Integer.MIN_VALUE;
            int high=nums[i]<Integer.MAX_VALUE-t? nums[i]+t:Integer.MAX_VALUE;
            if(bst.containsInRange(low,high))
            {
                return true;
            }
            else
            {
                bst.insert(nums[i]);
            }
        }
        
        return false;
    }

Log in to reply
 

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