本文主要是介绍Contains Duplicate III Java,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
题意及分析:
给出一个数组,要求判断是否存在,对于其中两个不同的元素有:(1) |i-j| <= k (2) |nums[i]-nums[j]| <= t。
TreeSet(binary search tree) o(Nlogk)
利用treeset,用floor方法查找treeSet中大于等于当前值且与当前元素距离小于t的最大元素,然后如果该元素不为空,那么就可以找到符合题意的两个元素。
或者用用ceiling方法查找treeSet中大于等于当前值且与当前元素距离小于t的最小元素,然后如果该元素不为空,那么就可以找到符合题意的两个元素。
最后需要注意的一点,就是两个元素之间的距离要小于等于k,即|i-j|<=k,所以当前treeSet中最多只能有k个元素
class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {if(nums==null||nums.length==0||k<=0) return false;TreeSet<Long> treeSet = new TreeSet<Long>();for(int i=0;i<nums.length;i++){final Long floor = treeSet.floor((long)nums[i]+t);final Long ceil = treeSet.ceiling((long)nums[i]-t);if((floor!=null&&floor>=(long)nums[i])||(ceil!=null&&ceil<=(long)nums[i])){return true;}treeSet.add((long)nums[i]);if(i>=k){ //因为元素的坐标差不能超过k,所以在treeSet中最多只能有k个元素treeSet.remove((long)nums[i-k]);}}return false;}
}
这篇关于Contains Duplicate III Java的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!