当前位置:首页 > 资讯 > info6 > 正文

Java TreeSet的使用 (LeetCode Contains Duplicate III )

发表于: 2015-06-03 ? 作者:chen476328361 ? 来源:转载 ? 浏览:
摘要: TreeSet中使用元素的自然顺序对元素进行排序,或者根据创建set时提供的Comparator进行排序,具体取决于使用的构造方法,其基本操作(add、remove和contains)的时间开销为log(n)。1.所在包java.util.TreeSet;2.构造方法(1)publicTreeSet()构造一个新的空set,该set根据其元素的自然顺序进行排序。(2)publicTreeSet(C

TreeSet中使用元素的自然顺序对元素进行排序,或者根据创建 set 时提供的 Comparator 进行排序,具体取决于使用的构造方法,其基本操作(add、remove 和 contains)的时间开销为 log(n) 。

1. 所在包

java.util.TreeSet;


2. 构造方法

(1) public TreeSet()

构造一个新的空 set,该 set 根据其元素的自然顺序进行排序。

(2) public TreeSet(Collection c)

构造一个包含指定 collection 元素的新 TreeSet,它按照其元素的自然顺序进行排序插入到该 set 的所有元素都必须能够由指定比较器进行相互比较。

(3) public TreeSet(Comparator comparator)

构造一个新的空 TreeSet,它根据指定比较器进行排序。插入到该 set 的所有元素都必须能够由指定比较器进行相互比较。

(4) public TreeSet(SortedSet s)

构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。


3. 常用方法

注:类型参数:E - 此 set 维护的元素的类型;

(1) public boolean add(E e)?

将指定的元素添加到此 set(如果该元素尚未存在于 set 中);如果此 set 已经包含这样的元素,则该调用不改变此 set 并返回 false。

(2) public boolean addAll(Collection c)

将指定 collection 中的所有元素添加到此 set 中。

(3) public E ceiling(E e)?

返回此 set 中大于等于给定元素的最小元素;如果不存在这样的元素,则返回 null。

(4) public void clear()?

移除此 set 中的所有元素。在此调用返回之后,set 将为空。?

(5) public Object clone()

返回 TreeSet 实例的浅表副本。(这些元素本身不被复制。)

(6) public Comparatorcomparator()

返回对此 set 中的元素进行排序的比较器;如果此 set 使用其元素的自然顺序,则返回 null。

(7) public boolean contains(Object o)

如果此 set 包含指定的元素,则返回 true。

(8) public Iterator descendingIterator()

返回在此 set 元素上按降序进行迭代的迭代器。

(9) NavigableSet descendingSet()?

返回此 set 中所包含元素的逆序视图。

(10) E first()?

返回此 set 中当前第一个(最低)元素。

(11) E floor(E e)?

返回此 set 中小于等于给定元素的最大元素;如果不存在这样的元素,则返回 null。

(12) SortedSet headSet(E toElement)?

返回此 set 的部分视图,其元素严格小于 toElement。

(13) NavigableSet headSet(E toElement, boolean inclusive)?

返回此 set 的部分视图,其元素小于(或等于,如果 inclusive 为 true)toElement。

(14) E higher(E e)?

返回此 set 中严格大于给定元素的最小元素;如果不存在这样的元素,则返回 null。

(15) boolean isEmpty()?

如果此 set 不包含任何元素,则返回 true。

(16) Iterator iterator()?

返回在此 set 中的元素上按升序进行迭代的迭代器。

(17) E last()?

返回此 set 中当前最后一个(最高)元素。

(18) E lower(E e)?

返回此 set 中严格小于给定元素的最大元素;如果不存在这样的元素,则返回 null。

(19) E pollFirst()?

获取并移除第一个(最低)元素;如果此 set 为空,则返回 null。

(20) E pollLast()?

获取并移除最后一个(最高)元素;如果此 set 为空,则返回 null。

(21) boolean remove(Object o)?

将指定的元素从 set 中移除(如果该元素存在于此 set 中)。

(22) int size()?

返回 set 中的元素数(set 的容量)。

(23) NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

返回此 set 的部分视图,其元素范围从 fromElement 到 toElement。

(24) SortedSet subSet(E fromElement, E toElement)?

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

(25) SortedSet tailSet(E fromElement)?

返回此 set 的部分视图,其元素大于等于 fromElement。

(26) NavigableSet tailSet(E fromElement, boolean inclusive)?

返回此 set 的部分视图,其元素大于(或等于,如果 inclusive 为 true)fromElement。


4. 以LeetCode 的第?220题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.

代码:(时间复杂度 nlogk)

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    	TreeSet ts = new TreeSet();
        for(int i=0; i=0) ts.remove((long)nums[i-k-1]);
           Long tmp = ts.ceiling((long) nums[i]);
           if(tmp!=null && t>=Math.abs(tmp-nums[i])) return true;
           tmp = ts.floor((long) nums[i]);
           if(tmp!=null && t>=Math.abs(nums[i]-tmp) ) return true;
           ts.add((long) nums[i]);
        }
        return false;
    }
}

Java TreeSet的使用 (LeetCode Contains Duplicate III )

版权所有 IT知识库 CopyRight ? 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号