一、TreeMap

TreeMap按照key進(jìn)行排序

TreeMap底層是根據(jù)紅黑樹的數(shù)據(jù)結(jié)構(gòu)構(gòu)建的，默認(rèn)是根據(jù)key的自然排序來(lái)組織（比如integer的大小，String的字典排序）

TreeMap<Integer,Integer> map1 = new TreeMap<Integer,Integer>(); //默認(rèn)的TreeMap升序排列 TreeMap<Integer,Integer> map2= new TreeMap<Integer,Integer>(new Comparator<Integer>(){/* * int compare(Object o1, Object o2) 返回一個(gè)基本類型的整型， * 返回負(fù)數(shù)表示：o1 小于o2， * 返回0 表示：o1和o2相等， * 返回正數(shù)表示：o1大于o2。 */ public int compare(Integer a,Integer b){return b-a; }});

2. TreeMap按照value進(jìn)行排序

TreeMap只能根據(jù)key來(lái)排序，是不能根據(jù)value來(lái)排序的（否則key來(lái)排序根本就不能形成TreeMap）。如果要根據(jù)treeMap中的value排序。所以網(wǎng)上看了一下，大致的思路是把TreeMap的EntrySet轉(zhuǎn)換成list，然后使用Collections.sort排序。

CompareTo方法的簡(jiǎn)單介紹

CompareTo：方法主要可以對(duì) Byte, Double, Integer, Float, Long 或 Short 類型的參數(shù) 進(jìn)行比較：
指定的數(shù)與參數(shù)相等返回 0；
指定的數(shù)小于參數(shù)返回-1；
指定的數(shù)大于參數(shù)返回1；

實(shí)戰(zhàn)：股票價(jià)格的波動(dòng)

力扣https://leetcode-cn.com/problems/stock-price-fluctuation/

class StockPrice {/*** 記錄時(shí)間戳到價(jià)格的映射*/private Map<Integer, Integer> map;/*** 記錄某個(gè)價(jià)格出現(xiàn)過(guò)幾次* 可以方便地返回最大價(jià)格和最小價(jià)格*/private TreeMap<Integer, Integer> treeMap;/*** 記錄最大的時(shí)間戳*/private int maxTimestamp;public StockPrice() {this.map = new HashMap<>();this.treeMap = new TreeMap<>();this.maxTimestamp = 0;}public void update(int timestamp, int price) {// 記錄新時(shí)間戳到價(jià)格的映射Integer oldPrice = map.put(timestamp, price);// 如果存在舊價(jià)格，則舊價(jià)格的次數(shù)減一// 如果舊價(jià)格只出現(xiàn)過(guò)一次，直接移除if (oldPrice != null) {int oldCount = treeMap.get(oldPrice);if (oldCount == 1) {treeMap.remove(oldPrice);} else {treeMap.put(oldPrice, oldCount - 1);}}// 更新新價(jià)格的次數(shù)treeMap.put(price, treeMap.getOrDefault(price, 0) + 1);// 記錄最大時(shí)間戳if (timestamp > maxTimestamp) {maxTimestamp = timestamp;}}public int current() {return map.get(maxTimestamp);}public int maximum() {return treeMap.lastKey();}public int minimum() {return treeMap.firstKey();} }

二、大頂堆、小頂堆

java使用PriorityQueue（優(yōu)先隊(duì)列），一個(gè)基于優(yōu)先級(jí)堆的無(wú)界優(yōu)先級(jí)隊(duì)列。

實(shí)際上是一個(gè)堆（不指定Comparator時(shí)默認(rèn)為最小堆），通過(guò)傳入自定義的Comparator函數(shù)可以實(shí)現(xiàn)大頂堆。

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //小頂堆，默認(rèn)容量為11 PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>(){ //大頂堆，容量11@Overridepublic int compare(Integer i1,Integer i2){return i2-i1;} });

PriorityQueue的常用方法有：poll(),offer(Object),size(),peek()等。

• 　　插入方法（offer()、poll()、remove() 、add() 方法）時(shí)間復(fù)雜度為O(log(n)) ；
• 　　remove(Object)?和?contains(Object) 時(shí)間復(fù)雜度為O(n)；
• 　　檢索方法（peek、element?和?size）時(shí)間復(fù)雜度為常量。

?PriorityQueue的API文檔說(shuō)明：

構(gòu)造方法摘要

PriorityQueue() ??????????使用默認(rèn)的初始容量（11）創(chuàng)建一個(gè)?PriorityQueue，并根據(jù)其自然順序?qū)υ剡M(jìn)行排序。

PriorityQueue(Collection<? extends?E>?c) ??????????創(chuàng)建包含指定 collection 中元素的?PriorityQueue。

PriorityQueue(int?initialCapacity) ??????????使用指定的初始容量創(chuàng)建一個(gè)?PriorityQueue，并根據(jù)其自然順序?qū)υ剡M(jìn)行排序。

PriorityQueue(int?initialCapacity,?Comparator<? super?E>?comparator) ??????????使用指定的初始容量創(chuàng)建一個(gè)?PriorityQueue，并根據(jù)指定的比較器對(duì)元素進(jìn)行排序。

PriorityQueue(PriorityQueue<? extends?E>?c) ??????????創(chuàng)建包含指定優(yōu)先級(jí)隊(duì)列元素的?PriorityQueue。

PriorityQueue(SortedSet<? extends?E>?c) ??????????創(chuàng)建包含指定有序 set 元素的?PriorityQueue。

?

方法摘要

?boolean	add(E?e) ??????????將指定的元素插入此優(yōu)先級(jí)隊(duì)列。
?void	clear() ??????????從此優(yōu)先級(jí)隊(duì)列中移除所有元素。
?Comparator<? super?E>	comparator() ??????????返回用來(lái)對(duì)此隊(duì)列中的元素進(jìn)行排序的比較器；如果此隊(duì)列根據(jù)其元素的自然順序進(jìn)行排序，則返回?null。
?boolean	contains(Object?o) ??????????如果此隊(duì)列包含指定的元素，則返回?true。
?Iterator<E>	iterator() ??????????返回在此隊(duì)列中的元素上進(jìn)行迭代的迭代器。
?boolean	offer(E?e) ??????????將指定的元素插入此優(yōu)先級(jí)隊(duì)列。
?E	peek() ??????????獲取但不移除此隊(duì)列的頭；如果此隊(duì)列為空，則返回?null。
?E	poll() ??????????獲取并移除此隊(duì)列的頭，如果此隊(duì)列為空，則返回?null。
?boolean	remove(Object?o) ??????????從此隊(duì)列中移除指定元素的單個(gè)實(shí)例（如果存在）。
?int	size() ??????????返回此 collection 中的元素?cái)?shù)。
?Object[]	toArray() ??????????返回一個(gè)包含此隊(duì)列所有元素的數(shù)組。
<T> T[]	toArray(T[]?a) ??????????返回一個(gè)包含此隊(duì)列所有元素的數(shù)組；返回?cái)?shù)組的運(yùn)行時(shí)類型是指定數(shù)組的類型。

從類 java.util.AbstractQueue?繼承的方法

addAll,?element,?remove

從類 java.util.AbstractCollection?繼承的方法

containsAll,?isEmpty,?removeAll,?retainAll,?toString

從類 java.lang.Object?繼承的方法

clone,?equals,?finalize,?getClass,?hashCode,?notify,?notifyAll,?wait,?wait,?wait

從接口 java.util.Collection?繼承的方法

containsAll,?equals,?hashCode,?isEmpty,?removeAll,?retainAll

還是上面那道題

class StockPrice {/*** 記錄時(shí)間到價(jià)格的映射*/private Map<Integer, Price> map;/*** 小頂堆，最小的價(jià)格在堆頂*/private PriorityQueue<Price> minHeap;/*** 大頂堆，最大的價(jià)格在堆頂*/private PriorityQueue<Price> maxHeap;/*** 記錄最大的時(shí)間戳*/private int maxTimestamp;public StockPrice() {this.map = new HashMap<>();this.minHeap = new PriorityQueue<>((p1, p2) -> p1.price - p2.price);this.maxHeap = new PriorityQueue<>((p1, p2) -> p2.price - p1.price);this.maxTimestamp = 0;}public void update(int timestamp, int price) {// 新的價(jià)格Price p = new Price(price);// 判斷舊的價(jià)格是否存在，存在的話把它更新成是錯(cuò)誤的價(jià)格Price oldP = map.put(timestamp, p);if (oldP != null) {oldP.error = true;}// 添加到小頂堆和大頂堆minHeap.offer(p);maxHeap.offer(p);// 記錄最大時(shí)間戳if (timestamp > maxTimestamp) {maxTimestamp = timestamp;}}public int current() {// 返回最大時(shí)間戳處的價(jià)格return map.get(maxTimestamp).price;}public int maximum() {// 把堆頂非最新的價(jià)格移除while (!maxHeap.isEmpty() && maxHeap.peek().error) {maxHeap.poll();}// 返回堆頂最大的價(jià)格return maxHeap.peek().price;}public int minimum() {// 把堆頂非最新的價(jià)格移除while (!minHeap.isEmpty() && minHeap.peek().error) {minHeap.poll();}// 返回堆頂最小的價(jià)格return minHeap.peek().price;}/*** 定義一個(gè)價(jià)格類，這個(gè)類記錄著這個(gè)價(jià)格是不是錯(cuò)誤的*/private static class Price {boolean error;int price;Price(int price) {this.price = price;this.error = false;}} }

總結(jié)

以上是生活随笔為你收集整理的力扣刷题之有序集合的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。