當前位置:首頁 > 資訊 > 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<? extends E> c)

構造一個包含指定 collection 元素的新 TreeSet,它按照其元素的自然順序進行排序插入到該 set 的所有元素都必須能夠由指定比較器進行相互比較。

(3) public TreeSet(Comparator<? super E> comparator)

構造一個新的空 TreeSet,它根據指定比較器進行排序。插入到該 set 的所有元素都必須能夠由指定比較器進行相互比較。

(4) public TreeSet(SortedSet<E> s)

構造一個與指定有序 set 具有相同映射關系和相同排序的新 TreeSet。


3. 常用方法

注:類型參數:E - 此 set 維護的元素的類型;

(1) public boolean add(E e) 

將指定的元素添加到此 set(如果該元素尚未存在于 set 中);如果此 set 已經包含這樣的元素,則該調用不改變此 set 并返回 false。

(2) public boolean addAll(Collection<? extends E> c)

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

(3) public E ceiling(E e) 

返回此 set 中大于等于給定元素的最小元素;如果不存在這樣的元素,則返回 null。

(4) public void clear() 

移除此 set 中的所有元素。在此調用返回之后,set 將為空。 

(5) public Object clone()

返回 TreeSet 實例的淺表副本。(這些元素本身不被復制。)

(6) public Comparator<? super E>comparator()

返回對此 set 中的元素進行排序的比較器;如果此 set 使用其元素的自然順序,則返回 null。

(7) public boolean contains(Object o)

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

(8) public Iterator<E> descendingIterator()

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

(9) NavigableSet<E> descendingSet() 

返回此 set 中所包含元素的逆序視圖。

(10) E first(

返回此 set 中當前第一個(最低)元素。

(11) E floor(E e) 

返回此 set 中小于等于給定元素的最大元素;如果不存在這樣的元素,則返回 null。

(12) SortedSet<E> headSet(E toElement) 

返回此 set 的部分視圖,其元素嚴格小于 toElement。

(13) NavigableSet<E> headSet(E toElement, boolean inclusive) 

返回此 set 的部分視圖,其元素小于(或等于,如果 inclusive 為 true)toElement。

(14) E higher(E e) 

返回此 set 中嚴格大于給定元素的最小元素;如果不存在這樣的元素,則返回 null。

(15) boolean isEmpty() 

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

(16) Iterator<E> 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<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

返回此 set 的部分視圖,其元素范圍從 fromElement 到 toElement。

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

返回此 set 的部分視圖,其元素從 fromElement(包括)到 toElement(不包括)。

(25) SortedSet<E> tailSet(E fromElement) 

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

(26) NavigableSet<E> 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<Long> ts = new TreeSet<Long>();
        for(int i=0; i<nums.length; i++) {
           if(i-k-1>=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號
广东25选5开奖结果