java 数据结构 Map和Set

目录

搜索树

操作-查找

操作-插入

操作-删除(难点)

Map

Map 的常用方法

Set 

哈希表

哈希函数

哈希冲突

冲突-避免-负载因子调节(重点掌握)

冲突-解决

冲突-解决-开散列/哈希桶(重点掌握)

实现HashBuck类

put方法

resize()扩容方法

hasCode方法

自定义哈希表

OJ练习


搜索树

TreeMap和TreeSet底层是二叉搜索树

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
  
若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  
若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

  
它的左右子树也分别为二叉搜索树


操作-查找

图解


思路:二叉搜索树它的左边节点的值都是小于这个根节点的,右边节点都是大于根节点的,子树也

是一样所以找的时候设置一个变量cur在根节点先,然后while循环cur往下走,往哪里走呢,if语句

判断cur的val值跟要找的值进行比较,大于走右边,小于走左边,等于说明找到了,其他情况说明

没找到


代码实现:

 public boolean search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < key) {
                cur = cur.right;
            } else if (cur.val > key) {
                cur = cur.left;
            } else {
                return true;
            }
        }
        return false;
    }

操作-插入

图解


思路:同样设置一个变量cur,还得设置一个变量parent为空,同样while循环,判断要插入的值跟

根节点进行比较,大于走右边,小于走左边,等于直接返回false,在cur往下走之前,parent走到

cur的位置,然后cur走到空了,parent还停留在cur的上一个节点,然后判断parent当前节点的值和

要插入的值进行比较,大的插右边,小的话插左边,等于返回false

代码实现:

    public boolean insert(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                //有一个相同的就够了 这是二叉搜索树
                return false;
            }
        }
        TreeNode node = new TreeNode(val);
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        //走到这 说明插入成功
        return true;
    }

操作-删除(难点)

首先,我们要先走到要删除的结点,跟插入一样我们需要设置一个变量记录cur结点,当cur结点的

值和我们要删除的值一样的时候我们开始真正删除结点。

代码实现:

    public void remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else {
                //开始删除结点
                //cur表示要删除的结点
                //parent表示要删除结点的父亲结点
                removeNode(cur, parent);
            }
        }
    }

然后我们要分左右空不空的情况

图解

代码实现:

    private void removeNode(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        }

接着我们要考虑删除这个结点后还满不满足二叉搜索树的性质,所以我们需要用到替换法

图解

什么意思呢?就是要删除的节点,你删除了还得满足二叉搜索树的性质,就是左边的值都是小于根节点的值,右边都是大于根节点值

所以要找比左边都大,就找要删除节点的子树中最大的值,也就是最右边的数据,因为对于子树来说也是一样的道理,左边都是小于根节点的值,右边都是大于根节点的值

所以右边也是一个道理,找右边最小的值,也就是右树最左边的数据,因为对于要删除的根节点的右边节点的最小值都是大于左边节点的最大值

总结:上面的意思就是找合适的节点替换掉要删除的节点,可以从要删除节点的左边找最右边的,也可以找要删除节点的右边找最左边的

然后找到合适的数据之后,直接替换掉要删除的节点如图中的cur节点,然后删除那个合适的数据节点就行了

疑问:对于要删除的那个合适的数据节点也有左节点呢?

答案是没有,因为如图所示,我们要找的合适的数据是右树里面最小的数据,也就是右树最左边的数据了,对于这个节点来说就没有左节点了

怎么删合适的数据节点?怎么替换?

思路:设置一个变量tp先记录在cur的位置,设置一个变量t先记录cur的右边,然后while循环以t左边不为空为条件,就是t一直走到空,说明这个就是合适的数据节点,然后tp走到t的位置,t往t的左边走,然后走到空,把这个合适的数据节点的值给到要删除的节点的值,也就是替换掉。

然后要分情况执行下面的操作了,如果tp的左边==t说明左边有节点,那就执行tp.left=t.right,因为替换掉,要把这个合适的数据节点删掉。然后如果左边没有节点,说明是单分支,就执行tp.right=t.right

删除全部代码实现:

    private void removeNode(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            //说明左右都不为空
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            //要删除的结点 替换成合适的数据结点的值
            cur.val = target.val;
            //删除合适的数据结点
            if (targetParent.left == target) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }
}

Map

Map是一个接口类,该类没有继承自Collection,该类中存储的是<K,V>结构的键值对,并且K一

定是唯一的,不能重复

HaspMap和TreeMap不支持迭代器遍历的,因为没有实现iterable接口,只能通过转换成set然后

用迭代器去遍历set


Map 的常用方法

代码实现:

    public static void main2(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();//底层是一个二叉搜索树,查找的时间复杂度O(logN)
        Map<String, Integer> map2 = new HashMap<>();//底层是一个二叉搜索树,查找的时间复杂度O(1)
        //拿什么比较大小的呢? 拿我们的key
        map.put("mike", 3);
        map.put("sunny", 2);
        map.put("demo", 5);

        //get方法返回的是value,通过key返回对应的value值
        Integer value = map.get("mike");
        System.out.println(value);

        //这个方法,当你去获取这个key所对应的value的时候,如果没有就返回你默认的value 也就是下面的999
        Integer value1 = map.getOrDefault("demo2", 999);
        System.out.println(value1);

        //Set<Key> set = map.keySet();
        Set<String> set = map.keySet();
        System.out.println(set);

        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();

        for (Map.Entry<String, Integer> entry : entrySet) {
            System.out.println("key :" + entry.getKey() + "value :" + entry.getValue());
        }

    }


注意:
1. Map是一个接口,不能直接实例化对象,如果要实例化对象只能实例化其实现类TreeMap或者HashMap


2. Map中存放键值对的Key是唯一的,value是可以重复的key如果有重复的,原来的会被覆盖掉


3. 在TreeMap中插入键值对时,key不能为空,否则就会抛NullPointerException异常,value可以为空。但是HashMap的key和value都可以为空。


4. Map中的Key可以全部分离出来,存储到Set中来进行访问(因为Key不能重复)。


5. Map中的value可以全部分离出来,存储在Collection的任何一个子集合中(value可能有重复)。


6. Map中键值对的Key不能直接修改,value可以修改,如果要修改key,只能先将该key删除掉,然后再来进行重新插入。


Set 


Set与Map主要的不同有两点:Set是继承自Collection的接口类,Set中只存储了Key

HashSet底层是一个HashMap,每次存储元素的时候 默认的value其实是一个object对象

常用方法实现:

    public static void main3(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("mike");
        set.add("hello");
        set.add("3");
        //输出的无序
        System.out.println(set);

        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }

注意:
1. Set是继承自Collection的一个接口类


2. Set中只存储了key,并且要求key一定要唯一


3. TreeSet的底层是使用Map来实现的,其使用key与Object的一个默认对象作为键值对插入到Map中的


4. Set最大的功能就是对集合中的元素进行去重


5. 实现Set接口的常用类有TreeSet和HashSet,还有一个LinkedHashSet,LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。


6. Set中的Key不能修改,如果要修改,先将原来的删除掉,然后再重新插入


7. TreeSet中不能插入null的key,HashSet可以


哈希表

概念:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过

某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时

通过该函数可以很快找到该元素。

当向该结构中:
 1.插入元素:
根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
  2.搜索元素:
对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功

该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称

为哈希表(HashTable)(或者称散列表)


哈希函数

设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小

图解


哈希冲突

不同关键字key通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞

不同的关键字key,通过相同的哈希函数得到了相同的值

冲突的发生是必然的,但我们能做的应该是尽量的降低冲突率

冲突-避免-负载因子调节(重点掌握)

负载因子和冲突率的关系粗略演示

所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率。

已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。


冲突-解决

解决哈希冲突两种常见的方法是:闭散列开散列


闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去


线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止

图解


二次探测

图解


图中H0表示发生冲突的下标,然后i表示发生冲突的次数,m表示数组的长度,计算出后得到这个

数,然后插入


冲突-解决-开散列/哈希桶(重点掌握)

开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关

键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链

表的头结点存储在哈希表中。

图解

从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。

实现HashBuck类

开散列法中的数组可以理解为数组中的每一个下标存的都是头节点,一开始下标都是null,然后节

点分为三个域,key域存的是发生冲突元素的下标,val域存的就是值,next域存的就是下一个节点

的地址

代码实现:

    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    //链表数组
    public Node[] array;
    public int usedSize;
    //负载因子
    public static final float loadFactor = 0.75f;

    //初始化数组
    public HashBuck2() {
        array = new Node[10];
    }

put方法


思路:put方法我们先计算这个key要放在哪个index下标,然后把这个下标的地址赋给一个Node节点的变量cur,然后while循环,这里我们用的是尾插法先设置一个Node节点变量tail用来记录cur节点,然后开始循环判断这个链表里有没有这个key,有的话我们就更新一下val值,没有的话我们创建一个节点node,利用尾插法去加入这个节点,利用刚才的变量tail,如果tail不为空,它的next域存的就是node节点的地址,然后我们设置尾节点为node,如果为空,我们直接存在该数组下标存node的地址并且把node的next域置为空

代码实现:

    //尾插法
    public void putTail(int key, int val) {
        int index = key % array.length;
        Node cur = array[index];//array[index]可以理解为地址,因为数组的每个元素 就是这个链表的头节点
        Node tail = null;
        //遍历index下标的链表 是否存在key 存在更新value值
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            tail = cur;
            cur = cur.next;
        }
        //走到这说明没有找到这个key
        //这里用尾插法
        Node node = new Node(key, val);
        if (tail != null) {
            tail.next = node;
            node.next = null;
        } else {
            array[index] = node;
            node.next = null;
        }
        usedSize++;
        //判断负载因子是不是大于0.75
        if (doLoadFactor() > loadFactor) {
            //进行扩容
            resize();
        }
    }
    //计算负载因子
    private float doLoadFactor() {
        return usedSize * 1.0f / array.length;
    }

resize()扩容方法

哈希冲突进行扩容时需要注意原来HasMap里面的所有元素,数组下的每一个节点都要去重新计算

它在新数组当中的位置


思路:就是原数组位置冲突的元素,都要进行重新哈希,也就是重新计算下标,放到新数组的其他位置,比如本来原数组的长度为10,要放一个13,然后13%10=13,本来应该放到13的下标,但是长度只有10,所以放到3下标,但是经过扩容后,有13下标了这个发生冲突的元素就可以放到新数组的13下标了,然后它后面的其他节点也要进行重新计算,然后放到新数组其他的位置去

扩容方法我们先创建一个数组,大小为原来数组的两倍,然后遍历原来的数组,然后还是一样设置一个节点变量cur把数组下标的地址赋给它,然后遍历下标的链表,遍历这个链表的第一步先设置一个变量tmp走到当前节点的下一个节点就是tmp=cur.next,然后我们要重新计算每个发生冲突元素的下标,也就是每个节点的key,判断扩容后它还是不是要在原来的下标下存储着

设置一个变量newIndex记录一下新的下标,然后进行尾插法,然后判断新数组newIndex下标是不是空,然后把新数组newIndex下标下的头节点赋给设置的一个变量tail,然后while循环以tail.next为不为空,不为空,我们while循环遍历这个链表直到tail.next为空,tail.next为空了然后我们把tail.next=cur让它的next域装cur的地址,并且把cur.next=null置为空,这样确保是尾节点,然后如果新数组newIndex下标上来就是空,我们直接让新数组的newIndex装cur的地址,并且也cur.next=null置为空,然后让cur往下个节点走,把刚才的tmp的地址赋给cur


代码实现:

    private void resize() {
        //新数组是原来数组的两倍大小
        Node[] newArray = new Node[2 * array.length];
        //循环原来的数组
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            //循环链表
            while (cur != null) {
                Node tmp = cur.next;//记录下一个结点
                int newIndex = cur.key % newArray.length;//新的数组下标
                if (newArray[newIndex] != null) {
                    Node tail = newArray[newIndex];
                    while (tail.next != null) {
                        tail = tail.next;
                    }
                    tail.next = cur;
                    cur.next = null;
                } else {
                    newArray[newIndex] = cur;
                    cur.next = null;
                }
                cur = tmp;
            }
        }
        //最后原数组指向新数组
        array = newArray;
    }


hasCode方法

我们认为两个名字相同,年龄相同的对象,将存储在同一个位置,如果不重写hashcode()方法,

我们可以来看代码:

class Person {
    public String name;
    public int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

public class Test1 {
    public static void main(String[] args) {
        Person per1 = new Person("gaobo", 20);
        Person per2 = new Person("gaobo", 20);
        System.out.println(per1.hashCode());
        System.out.println(per2.hashCode());
    }
}
//执行结果
460141958
1163157884

注意:两个对象的hash值不一样

加一个hasCode方法后我们可以来看代码:

class Person {
    public String name;
    public int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

public class Test1 {
    public static void main(String[] args) {
        Person per1 = new Person("gaobo", 20);
        Person per2 = new Person("gaobo", 20);
        System.out.println(per1.hashCode());
        System.out.println(per2.hashCode());
    }
}
//执行结果
460141958
460141958

注意:哈希值一样

结论:

1、hashcode方法用来确定对象在内存中存储的位置是否相同

2、事实上hashCode() 在散列表中才有用,在其它情况下没用。在散列表中hashCode() 的作用

是获取对象的 散列码,进而确定该对象在散列表中的位置。


自定义哈希表

能够作为泛型参数的只能是引用类型,不能是基本数据类型


代码实现:

public class HashBuck3<K, V> {
    static class Node<K, V> {
        public K key;
        public V val;
        public Node<K, V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node<K, V>[] array;
    public int usedSize;

    public HashBuck3() {
        array = (Node<K, V>[]) new Node[10];
    }

    public void put(K key, V val) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];
        Node<K, V> prev = null;
        while (cur != null) {
            //这里是引用类型 记得用equals比较
            if (cur.key.equals(key)) {
                cur.val = val;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
        Node<K, V> node = new Node<>(key, val);
        if (prev != null) {
            prev.next = node;
            node.next = node;
        } else {
            array[index] = node;
            node.next = null;
        }
        usedSize++;
    }

    //根据key获取values
    public V getVal(K key) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];
        while (cur != null) {
            //这里是引用类型 记得用equals比较
            if (cur.key.equals(key)) {
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }

}


总结:

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set

2. java 中使用的是哈希桶方式解决冲突的

3. java 会在冲突链表长度大于一定阈值后,将链表转变为搜索树(红黑树)

4. java 中计算哈希值实际上是调用的类的 hashCode 方法,进行 key 的相等性比较是调用 key 的

equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值,必须覆写

hashCode 和 equals 方法,而且要做到 equals 相等的对象,hashCode 一定是一致的。


OJ练习

只出现一次的数字

136. 只出现一次的数字 - 力扣(LeetCode)

代码实现:

    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int x : nums) {
            if (!set.contains(x)) {
                set.add(x);
            } else {
                set.remove(x);
            }
        }
        for (int x : nums) {
            if (set.contains(x))
                return x;
        }
        return -1;
    }

复制带随机指针的链表

138. 随机链表的复制 - 力扣(LeetCode)

思路:利用map或者hashmap去做,先创建一个变量cur记录head结点,然后第一次遍历cur,每次遍历的时候创建一个结点,然后存进我们的map当中。第二次遍历把我们刚才创建的结点的next域和random域都串起来,我们知道map是键值对的,它的get方法根据key获取value,然后我们通过map.get(cur).next=map.get(cur.next);把创建的新结点的next域填入下一个结点的地址,random域也是一样,遍历完成后这个链表就串起来了,最后返回map.get(head)


代码实现:

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class Solution {
    //复制带随机指针的链表
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> hashMap = new HashMap<>();
        Node cur = head;
        //第一遍遍历 存储对应的关系
        while (cur != null) {
            Node node = new Node(cur.val);
            hashMap.put(cur, node);
            cur = cur.next;
        }
        //第二次遍历 修改每个结点的指向
        cur = head;
        while (cur != null) {
            hashMap.get(cur).next = hashMap.get(cur.next);
            hashMap.get(cur).random = hashMap.get(cur.random);
            cur = cur.next;
        }
        //返回head对应的地址
        return hashMap.get(head);
    }
}


宝石与石头

771. 宝石与石头 - 力扣(LeetCode)


思路:遍历宝石数组存进集合set当中,然后设置一个计数器,接着遍历石头数组,判断set集合里有没有这个字符,有的话计数器++,最后返回计算器

代码实现:

    //宝石与石头
    public static int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> hashSet = new HashSet<>();

        for (char ch : jewels.toCharArray()) {
            hashSet.add(ch);
        }
        int count = 0;
        for (char ch : stones.toCharArray()) {
            if (hashSet.contains(ch)) {
                count++;
            }
        }
        return count;
    }

旧键盘打字

旧键盘 (20)__牛客网 (nowcoder.com)

思路:遍历第二行输入的字符串,然后转化为数组存入set集合里,然后遍历第一行输入的字符串,判断set集合有没有,没有的话我们输出字符,但是题目要求坏的只输出一次,所以再创建一个集合set2,输出的要求改为两个集合中都没有这个字符才输出

代码实现:

    //旧键盘
    public static void main7(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String b = in.nextLine();
            func(a, b);
        }
    }

    private static void func(String a, String b) {
        HashSet<Character> hashSet = new HashSet<>();
        for (char ch : b.toUpperCase().toCharArray()) {
            hashSet.add(ch);
        }
        HashSet<Character> hashSet2 = new HashSet<>();
        for (char ch : a.toUpperCase().toCharArray()) {
            if (!hashSet.contains(ch) && !hashSet2.contains(ch)) {
                System.out.print(ch);
                hashSet2.add(ch);
            }
        }
    }


前K个高频单词

692. 前K个高频单词 - 力扣(LeetCode)


思路:首先创建一个map集合,然后我们遍历这个数组,然后判断map这个字符串有没有在map里面出现过,没有的话就加入,有的话我们只需要增加value值

接着创建一个堆,存储entry类型的变量,然后传入一个自定义的比较器,重写这个比较器,题目要求高到低排序,所以设置成小根堆,然后我们通过map.entrySet去遍历map,然后我们判断小根堆的长度是不是小于k,k表示前 k 个出现次数最多的单词,小于直接存进堆,大于k我们需要判断value值以及else单词出现的次数是不是一样多,设置一个变量top存储堆顶元素,然后通过top的value值和map的value值是不是一样,一样的话,我们还要以字典序进行排序,所以要判断key值,都满足的情况下,才出堆顶元素,然后存入map的entry元素

最后创建一个list集合,这个list集合存的是String类型的变量,然后遍历k的长度,然后创建一个变量top存取poll()堆的元素,然后list添加top.getKey的值,然后遍历完,调用Collections方法的翻转,把这个集合进行翻转


但是我们忽略了一个点,就是在堆存储元素的时候,如果字符串出现相同的次数的时候我们要以大根堆进行存储,不然后面进行翻转的时候会出错

代码实现:

    public static List<String> topKFrequent(String[] words, int k) {
        //先计算每个单词出现的对应的次数
        HashMap<String, Integer> map = new HashMap<>();
        for (String x : words) {
            //存储到map集合 判断为不为空
            if (map.get(x) == null) {
                map.put(x, 1);
            } else {
                Integer val = map.get(x);
                map.put(x, val + 1);
            }
        }

        //遍历好统计好的map 把每组数据存到小根堆当中 要设置一个自定义比较器
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    //在加入元素的时候 如果相同的次数 转为大根堆 按照单词字典序排序
                    return o2.getKey().compareTo(o1.getKey());
                }
                //小根堆
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //遍历entry
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            //存入小根堆 要注意是不是相同的次数
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                //满了 开始进行比较
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    //不同的单词有相同出现频率  按字典顺序排序
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }

        //存入集合
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            list.add(top.getKey());
        }
        //翻转
        Collections.reverse(list);
        return list;
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515580.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++实现 “你被骗了” 自动拦截,反诈神器

“Never Gonna Give You Up” &#xff0c; 已经是历经十五年的名梗了&#xff0c;点开这个视频&#xff0c;就说明 你被骗了。 无论是自己点进了一些奇奇怪怪的链接&#xff0c;还是被自动跳转&#xff0c;你都不希望 展开 0x01 原理&规则 【本程序B站视频链接】快去B站…

layui框架实战案例(26):layui-carousel轮播组件添加多个Echarts图标的效果

在Layui中&#xff0c;使用layui-carousel轮播组件嵌套Echarts图表来实现多个图表的展示。 css层叠样式表 调整轮播图背景色为白色&#xff1b;调整当个Echarts图表显示loading…状态&#xff1b;同一个DIV轮播项目添加多个Echarts的 .layui-carousel {background-color: #f…

【图论】有向无环图中一个节点的所有祖先 - 邻接表(DFS)

文章目录 题目&#xff1a;有向无环图中一个节点的所有祖先题目描述代码与解题思路 题目&#xff1a;有向无环图中一个节点的所有祖先 2192. 有向无环图中一个节点的所有祖先 题目描述 代码与解题思路 func getAncestors(n int, edges [][]int) [][]int {g : make([][]int, …

C#清空窗体的背景图片

目录 一、涉及到的知识点 1.设置窗体的背景图 2.加载窗体背景图 3.清空窗体的背景图 二、 示例 一、涉及到的知识点 1.设置窗体的背景图 详见本文作者的其他文章&#xff1a;C#手动改变自制窗体的大小-CSDN博客 https://wenchm.blog.csdn.net/article/details/137027140…

链路追踪原理

分布式系统为什么需要链路追踪&#xff1f; 随着互联网业务快速扩展&#xff0c;软件架构也日益变得复杂&#xff0c;为了适应海量用户高并发请求&#xff0c;系统中越来越多的组件开始走向分布式化&#xff0c;如单体架构拆分为微服务、服务内缓存变为分布式缓存、服务组件通…

IDEA2023.1.1中文插件

1.启动IDEA 选中Customize 2.选择All settings 3.选中Plugins,再搜索栏里输入Chinese,找到 "Chinese (Simplified) Language"插件&#xff0c;点击 Install 进行安装。 4. 安装完成后&#xff0c;重启IntelliJ IDEA&#xff0c;即可看到界面语言已经变为中文。

HashMap为啥线程不安全?

1. HashMap1.7在多线程并发下扩容时&#xff0c;头插法会出现环。 /*** Rehashes the contents of this map into a new array with a* larger capacity. This method is called automatically when the* number of keys in this map reaches its threshold.** If current cap…

回溯算法|491.递增子序列

力扣题目链接 class Solution { private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {if (path.size() > 1) {result.push_back(path);// 注意这里不要加return&#xff0c;要取树上…

[计算机知识] TCP/IP网络模型、MySQL的结构

TCP/IP网络模型 应用层 给用户提供应用功能&#xff0c;如HTTP, DNS 应用层处于用户态&#xff0c;传输层及以下处于内核态 传输层 给应用层提供网络支持&#xff0c;如TCP, UDP TCP提供稳定、面向连接的网络传输协议 应用层的数据可能会太大&#xff0c;就需要进行拆分…

【GAMES101】Lecture08 09 Shading 3 (Texture Mapping cont.) 纹理映射 续集

目录 0 引言1 如何在三角形内进行插值&#xff1a;重心坐标1.1 为什么要在三角形内插值1.2 重心坐标1.3 使用重心坐标做三角形内颜色插值 2 应用纹理2.1 简单的纹理映射&#xff1a;漫反射2.2 问题&#xff1a;纹理放大&#xff08;采用插值解决&#xff09;2.2 点查询和范围查…

Qt主窗口 之:停靠/悬浮窗口(QDockWidget)

一、QDockWidget概述 QDockWidget 是 Qt 中的一个窗口部件&#xff0c;用于创建可停靠的窗口&#xff0c;通常用于构建多文档接口&#xff08;MDI&#xff09;或可定制的用户界面。QDockWidget 允许用户将窗口停靠在应用程序的主窗口周围&#xff0c;或将其拖动到独立的浮动窗…

STM32

GPIO通用输入输出口 GPIO:8种输入输出模式 浮空输入可读取引脚电平&#xff0c;若引脚悬空&#xff0c;电平不确定上拉输入可读取引脚电平&#xff0c;内部接上拉电阻&#xff0c;悬空时默认为高电平下拉输入可读取引脚电平&#xff0c;内部接下拉电阻&#xff0c;悬空时默认…

视频编辑的瑞士军刀,MoviePy库的详解与应用示例

左手编程&#xff0c;右手年华。大家好&#xff0c;我是一点&#xff0c;关注我&#xff0c;带你走入编程的世界。 公众号&#xff1a;一点sir&#xff0c;关注领取python编程资料 在数字媒体的时代&#xff0c;视频内容的创作和编辑变得越来越重要。无论是社交媒体上的短视频&…

【数据结构】初识数据结构与复杂度总结

前言 C语言这块算是总结完了&#xff0c;那从本篇开始就是步入一个新的大章——数据结构&#xff0c;这篇我们先来认识一下数据结构有关知识&#xff0c;以及复杂度的相关知识 个人主页&#xff1a;小张同学zkf 若有问题 评论区见 感兴趣就关注一下吧 目录 1.什么是数据结构 2.…

原创【matcap材质在ue4中的实现办法】

matcap材质在ue4中的实现办法 2023-08-29 15:34 https://www.bilibili.com/video/BV1GR4y1b76n/?spm_id_from333.337.search-card.all.click&vd_sourced76b773892c830a157c0ccc97ba78411 评论(0)

PS从入门到精通视频各类教程整理全集,包含素材、作业等(8)复发

PS从入门到精通视频各类教程整理全集&#xff0c;包含素材、作业等 最新PS以及插件合集&#xff0c;可在我以往文章中找到 由于阿里云盘有分享次受限制和文件大小限制&#xff0c;今天先分享到这里&#xff0c;后续持续更新 B站-PS异闻录&#xff1a;萌新系统入门课课程视频 …

Golang学习系列1-pprof性能调优

1. pprof 简述 一位亦师亦友的话让我记忆犹新&#xff0c;他说“学习一个新事务&#xff0c;应该从三个方面入手what,why,how;且三者的重要程度应该是递减”。所以在本文的第一部分先叙述下pprof的what & why。 1.1 What&#xff1f; pprof是golang自身提供的一种性能分…

基于顺序表的学生成绩管理系统

&#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;python从入门到精通&#xff0c;魔法指针&#xff0c;进阶C&#xff0c;C语言&#xff0c;C语言题集&#xff0c;C语言实现游戏&#x1f448; 希望得到您的订阅和支持~ &#x1f4a1; 坚持创作博文…

【Flink技术原理构造及特性】

1、Flink简介 Flink是一个批处理和流处理结合的统一计算框架&#xff0c;其核心是一个提供了数据分发以及并行化计算的流数据处理引擎。它的最大亮点是流处理&#xff0c;是业界最顶级的开源流处理引擎。 Flink最适合的应用场景是低时延的数据处理&#xff08;Data Processin…

算法练习—day1

title: 算法练习—day1 date: 2024-04-03 21:49:55 tags: 算法 categories:LeetCode typora-root-url: 算法练习—day1 网址&#xff1a;https://red568.github.io 704. 二分查找 题目&#xff1a; 题目分析&#xff1a; 左右指针分别为[left,right]&#xff0c;每次都取中…