亲宝软件园·资讯

展开

Java-TreeMap和Guava-HashMultiset

守林鸟 人气:0

一、Java-TreeMap

1.数据结构

底层数据结构是裸的红黑树,保证元素有序,没有比较器Comparator的情况按照key的自然排序,可自定义比较器。线程不安全。

可以存null,但是key不可以为null。

2.性能分析:空间换时间

增删改查的时间复杂度都是O(log n),HashMap的时间复杂度则是O(1),但是相比HashMap,TreeMap没有多余的空间,也没有负载因子。

2.几个查找方法

  • boolean containsValue(Object value):判断该TreeMap中是否包含有关指定value的映射
  • Map.Entry<K, V> firstEntry():返回该TreeMap的第一个(最小的)映射
  • K firstKey():返回该TreeMap的第一个(最小的)映射的key
  • Map.Entry<K, V> lastEntry():返回该TreeMap的最后一个(最大的)映射
  • K lastKey():返回该TreeMap的最后一个(最大的)映射的key
  • SortedMap<K, V> headMap(K toKey):返回该TreeMap中严格小于指定key的映射集合
  • SortedMap<K, V> subMap(K fromKey, K toKey):返回该TreeMap中指定范围的映射集合(大于等于fromKey,小于toKey)
  • Object ceilingKey(Object key);返回大于或等于给定键的最小键,如果没有这样的键则返回null
  • Object higherKey(Object key);返回严格大于指定键的最小键,没有则返回null
3.遍历
for (Map.Entry entry : treeMap.entrySet()) {
      System.out.println(entry);
}
Iterator iterator = treeMap.entrySet().iterator();
while (iterator.hasNext()) {
      System.out.println(iterator.next());
}

4.刷题杀招

  • Object ceilingKey(Object key);返回大于或等于给定键的最小键,如果没有这样的键则返回null
  • Object higherKey(Object key);返回严格大于指定键的最小键,没有则返回null
  • V getOrDefault(Object key, V defaultValue); 如果存在value则返回value,如果没有则返回defaultValue

map.put(key, map.getOrDefault(key,0)+1); 若有key则返回key的数量,如果没有则返回0,put的时候设置为1,达到对key计数的效果,相当于维护一个有序、可重复集合!

 
5.例题
力扣456. 132模式
题意:有一个长度为104的数组a,元素大小为109,判断有没有这样的子序列:i<j<k && a[i]<a[k]<a[j]
思路:遍历数组,将遍历到的每个数当作a[j]处理。
在遍历的过程中,去左边找a[i],去右边找a[k],首先满足第一个条件,索引i<j<k;
左边[0,j-1]找a[i],是最小值,那就在j遍历的过程中维护最小值;
右边[j+1,n-1]找a[k],是次小值,那么就找比a[i]大一点点即可,再与a[j]比较,右边维护一个有序集合,方便快速找值;
数组元素是109级别,不能用数组计数,则需要用map映射,没有说不重复,则需要计数,显然可以维护一个有序、可重复集合。
    /** 456. 132模式
     * 求是否存在子序列a[i],a[j],a[k]
     * i<j<k
     * a[i]<a[k]<a[j]
     * n<1e4  a[i]<1e9
     * 遍历数组,将遍历到的每个数当a[j]处理
     * 不看数组元素大小,只要遍历到的数在中间,就先满足了下标
     * 左边[0,j-1]是判断a[i]的,a[i]是最小的,那么就维护一个最小值
     * 右边[j+1,n-1]是判断a[k]的,a[k]是次小值,那就找比a[i]大一点点即可,再与a[j]比较
     */
    public boolean find132pattern(int[] a) {
        int n=a.length;
        if(n<3)
            return false;
        int minn=a[0];
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for(int k=2;k<n;k++){
            map.put(a[k], map.getOrDefault(a[k],0)+1);
            /**
             * map.getOrDefault(a[k],0)表示,如果a[k]存在就返回a[k]的值,否则返回0
             *一开始必然是返回0,设置value为1,随后逐渐增多,达到计数效果
             */
        }
        Integer ak=null;
        for(int j=1;j<n-1;j++){
            if(minn<a[j]){
                ak=map.higherKey(minn);
                if(ak!=null &&  ak<a[j]){
                    return true;
                }
            }
            minn=Math.min(minn,a[j]);
            if(map.get(a[j+1])==1){
                map.remove(a[j+1]);
            }else{
                map.put(a[j+1],map.get(a[j+1])-1);
            }
        }
        return false;
    }

 

 

二、Guava-HashMultiset

参考:https://www.cnblogs.com/qdhxhz/p/9410898.html

Guava是Goolge的库,不是jdk的,补充了一些集合类功能的不足。

1.先导入依赖包

        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>27.0-jre</version>
        </dependency> 

2.Multiset用法

Multiset是一个接口,没有实现java.util.Set接口,Set规定不可以放入相同元素,如果放入相同元素会被覆盖,Multiset相对于Set,可以添加相同元素。 

  • Multiset<Integer> set = HashMultiset.create();//创建方式不是用new
  • add(E e)//添加一个元素e
  • add(E e, int x)//添加x个元素e
  • remove(E e)//删除一个元素e
  • remove(E e, int x)//删除x个元素e
  • elementSet()//将不同的元素放入一个Set中
  • count(E e)//返回元素e的个数
  • setCount(E e ,int x)//指定集合里有x个元素e
  • setCount(E e,int x,int y)//如果恰好有x个e,则变为y,否则方法无效
  • retainAll(Collection c)//保留出现在给定集合参数的所有的元素,其他都不要
  • removeAll(Collection c)//去除出现给给定集合参数的所有的元素,有就去掉,没有不用管
  • size()//所有元素总个数

3.常用的实现了Multiset 接口的类

  • HashMultiset: 元素存放于 HashMap(决定了无序性)
  • LinkedHashMultiset: 元素存放于 LinkedHashMap,即元素的排列顺序由第一次放入的顺序决定
  • TreeMultiset:元素被排序存放于TreeMap
  • EnumMultiset: 元素必须是 enum 类型
  • ImmutableMultiset: 不可修改的 Mutiset 

4.遍历

        System.out.println("--遍历全部元素,包括重复的---");
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
        System.out.println("--只遍历key,不重复---");
        for(Integer key: set.elementSet()){
            System.out.println("key="+key+" cnt="+set.count(key));
        }

 

加载全部内容

相关教程
猜你喜欢
用户评论