[LeetCode-JAVA] Contains Duplicate III

题目:Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

 

思路:相比于I和II,稍微复杂,常规的思路,维护一个长为k的窗口,如果用循环判断会超时,考虑到问题的特性,用TreeSet中的相关方法来实现:

ceiling(e) : 返回set中大于或等于参数e的最小值,无则返回null;

floor(e) : 返回set中小于或等于参数e的最小值,无则返回null;

在k大小的范围内进行判断,每超过一个,从开头出remove一个值。

代码:

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<Long>();
        
        for(int i = 0 ; i < nums.length ; i++){
            if(i-k-1>=0) 
                set.remove((long)nums[i-k-1]);
            if(set.ceiling((long)nums[i]) != null){//大于等于nums[i]的最小元素
                long temp = set.ceiling((long)nums[i]);
                if(Math.abs(temp - nums[i]) <= t)
                    return true;
            }
            if(set.floor((long)nums[i]) != null){//大于等于nums[i]的最小元素
                long temp = set.floor((long)nums[i]);
                if(Math.abs(temp - nums[i]) <= t)
                    return true;
            }
            
            set.add((long)nums[i]);
        }
        return false;  
    }
}

 

又在网上看到更简洁的方法,也是利用TreeSet中的方法:

SortedSet<E> subSet(E fromElement, E toElement) 

返回此 set 的部分视图,其元素从 fromElement(包括)到 toElement(不包括)。

可以直接将两个判断化简在一起(不过LeetCode上没有过 cannot find symbol: class SortedSet 因此需要自己导入包,注意上面的import)。

代码:

import java.util.SortedSet;
public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(t<0) 
            return false;
        TreeSet<Long> set = new TreeSet<Long>();
        
        for(int i = 0 ; i < nums.length ; i++){
            if(i-k-1>=0) 
                set.remove((long)nums[i-k-1]);
                
            SortedSet<Long> subSet =  set.subSet((long)nums[i]-t, (long)nums[i]+t+1); 
            //t为负的话 fromKey > toKey 因此开始要判断
            if(!subSet.isEmpty()) return true; 
            
            set.add((long)nums[i]);
        }
        return false;  
    }
}

 

参考资料:http://blog.csdn.net/thinking2013/article/details/46336373

       http://blog.csdn.net/xudli/article/details/46323247

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。