Map和Set及其背后二叉搜索树的数据结构

转x33g5p2x  于2022-02-07 转载在 其他  
字(15.1k)|赞(0)|评价(0)|浏览(328)

在这篇博客当中介绍红黑树是因为TreeSet与TreeMap的底层数据结构是红黑树，而红黑树的基础是搜索树。虽然本章不讲红黑树，但是最为一个基础来了解。

一、二叉搜索树

在二叉搜索树类当中定义一个内部类Node，说明二叉搜索树是由结点构成的。

public static class Node {
        public int val;
        public Node left;
        public Node right;

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

1.二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

  1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  3. 它的左右子树也分别为二叉搜索树
  4. 二叉搜索树的中序遍历是有序的。

2.二叉搜索树的查找

因为二叉搜索树中的左结点比根结点的值小，右结点比根节点的值大，则从根开始遍历，如果比根结点的值小，则向左走；反之向右走。
代码：

public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if(cur.val == key) {
                return cur;
            }else if(cur.val < key) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return null;
    }

二叉搜索树的查找效率：

若在最好情况下，即根节点在左右树的中间并且左右子树都平衡。查找的时间复杂度为O(log2^N) 。因此最好的情况下该二叉搜索树是一个完全二叉树。
如：

若在最坏情况下，即根结点没有左子树或没有右子树。查找的时间复杂度为O(N) 。
如：

3.二叉搜索树的插入

二叉搜索树的插入不是为了存储，是为了满足二叉搜索树的性质。因此如果有一个值与二叉搜索树当中的某个结点的值相同，则不再存储。

需要注意的是，当我们正常遍历到一个合适的位置放入某个结点的值时，我们要的是上一个结点的左或者右结点放入该结点。如：

因为7比5大，则往右走。

因为7比8小，则往左走。

因为7比6大，往右走。此时发现root为空。因此root的位置就是该结点应该放入的位置。但是无法得到值为6的结点。因此要设置一个前驱结点来记录前面一个结点的位置。如果root已经为空，则放入的位置就应该由前驱结点判断它的值是否比前驱结点大，大则放右边，小则放左边。

public boolean insert(int key) {
        Node node = new Node(key);
        if(root == null) {
            root = node;
            return true;
        }

        Node cur = root;
        Node parent = null;

        while(cur != null) {
            if(cur.val == key) {
                return false;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //parent
        if(parent.val > key) {
            parent.left = node;
        }else {
            parent.right = node;
        }
        return true;
    }

4.二叉搜索树的删除(难点)

二叉搜索树如果要删除结点，有很多种情况。

首先来看第一种大情况。
设待删除的结点为cur，待删除的双亲结点为parent。

cur.left为空是大前提。
第一种小情况：
因为cur在根结点处，删除cur结点则根应该为cur结点的右节点。

第二种小情况：
cur结点是parent结点的左节点，则要删除cur结点时有parent.left = cur.right;。

第三种小情况：
cur结点是parent结点的右节点，则有parent.right = cur.right;

第二种大情况：

第一种小情况：
当cur为根时，并且cur.left为空，有root = cur.left;

第二种小情况：
当cur为parent的左节点时，有parent.left = cur.left;

第三种小情况：
当cur为parent的右节点时，则有parent.right = cur.left;

第三种大情况：

第一种小情况：
因为要删除cur结点，可以采用**“替罪羊”**的方式删除cur的值的结点，但不是直接删除cur的结点。

有两种找替罪羊的方法：
1.在待删除结点的右树的最左边的结点与待删除的结点的值交换。
2.在待删除结点的左树的最右边的结点与待删除的结点的值交换。

以下图为例：

我们可以设立两个标记：target和targetParent。以找cur结点的右树的最左结点为例，初始位置令targetParent指向cur，而target指向cur.right。遍历该子树的左树，当taget.left不为空时，证明找到了替罪羊。

初始：tp代表targetParent，t代表target。

先令tp指向t的位置，再将t向左遍历。此时t.left为空。

t.left为空时将t的值与cur的值交换，这样就转变上面第一种大情况下的t.left==null的问题，因此有tp.left=t.right。因为已经确定了t就是该子树的最左边结点。

第二种小情况：

因为t已经是cur.right的最左边的结点，因此若采用第一种小情况下的tp.left=t.right是不符合的。因此这种情况下只要将t的值与cur的值交换后，有tp.right=t.right即可。

public void remove(Node parent,Node cur) {
        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 {
            Node targetParent =  cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }

    public void removeKey(int key) {
        if(root == null) {
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                remove(parent,cur);
                return;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

5.二叉搜索树的基本操作代码汇总

class BinarySearchTree {

    public static class Node {
        public int val;
        public Node left;
        public Node right;

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

    public Node root;

    /**
     * 查找
     * @param key
     */
    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if(cur.val == key) {
                return cur;
            }else if(cur.val < key) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return null;
    }

    /**
     *
     * @param key
     * @return
     */
    public boolean insert(int key) {
        Node node = new Node(key);
        if(root == null) {
            root = node;
            return true;
        }

        Node cur = root;
        Node parent = null;

        while(cur != null) {
            if(cur.val == key) {
                return false;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //parent
        if(parent.val > key) {
            parent.left = node;
        }else {
            parent.right = node;
        }

        return true;
    }

    public void remove(Node parent,Node cur) {
        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 {
            Node targetParent =  cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }

    public void removeKey(int key) {
        if(root == null) {
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                remove(parent,cur);
                return;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }



}
public class TestDemo {

    public static void inorder(BinarySearchTree.Node root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(13);
        binarySearchTree.insert(1);
        binarySearchTree.insert(21);
        binarySearchTree.insert(14);
        binarySearchTree.insert(5);
        binarySearchTree.insert(6);

        inorder(binarySearchTree.root);
        System.out.println();//1 5 6 13 14 21 

        System.out.println(binarySearchTree.search(1).val);//1

        binarySearchTree.removeKey(13);

        inorder(binarySearchTree.root);
        System.out.println();//1 5 6 14 21
    }
}

二、集合Map的使用

1.关于Map的说明

Map在Java当中不被Collection实现，它是单独的一个接口，因此当要打印Map类型当中的元素时，不能使用迭代器打印。

该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

2.Map集合中常用的方法说明

方法解释
V get(Object key)返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)返回 key 对应的 value，key 不存在，返回默认值
V put(K key, V value)设置 key 对应的 value
V remove(Object key)删除 key 对应的映射关系
Set< K> keySet()返回所有 key 的不重复集合
Collection< V> values()返回所有 value 的可重复集合
Set<Map.Entry<K, V>> entrySet()返回所有的 key-value 映射关系
boolean containsKey(Object key)判断是否包含 key
boolean containsValue(Object value)判断是否包含 value

注意：

  1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
  2. Map中存放键值对的Key是唯一的，若再次put相同的Key的Value值，则Value会更新。
  3. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
  4. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
  5. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
  6. 打印map的时候打印的顺序可能不是按照put的顺序进行打印的。

3.Map中方法的详细说明

对于方法中的细节有：
1.调用getOrDefault方法时有Key则返回Key的Value值，没有Key则返回的是调用getOrDefault方法设置的默认的Value值。
2.调用put方法时Key和Value值都可以设置为null。
3.调用keySet()方法与values()。打印方式与结果

public class Test {
    public static void main(String[] args) {
        Map<String,String> map = new HashMap<>();
        map.put("及时雨1","宋江1");
        map.put("及时雨2","宋江2");
        Set<String> strings = map.keySet();
        System.out.println(strings);//[及时雨2, 及时雨1]
        Collection<String> collections = map.values();
        System.out.println(collections);//[宋江2, 宋江1]
    }
}

4.entrySet()方法的返回值类型是Set<Map.Entry<K, V>>，表面它是一个集合，集合里面的类型是键值对。

若一个变量是Map.Entry<K, V>类型，则它能够拿到该类型的Key值或者Value值。

有关于Map.Entry<K, V>类型的说明：
Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式。

方法解释
K getKey()返回 entry 中的 key
V getValue()返回 entry 中的 value
V setValue(V value)将键值对中的value替换为指定value

注意：Map.Entry<K,V>并没有提供设置Key的方法。

因此，有关于Map中entrySet的方法细节：

public class Test {
    public static void main(String[] args) {
        Map<String,String> map = new HashMap<>();
        map.put("及时雨1","宋江1");
        map.put("及时雨2","宋江2");
        Set<Map.Entry<String,String>> entrySet = map.entrySet();
        System.out.println(entrySet);
        System.out.println("======");
        for (Map.Entry<String,String> entry:entrySet) {
            System.out.println("key: "+entry.getKey()+" value: "+entry.getValue());
        }
    }
}
//打印结果
[及时雨2=宋江2, 及时雨1=宋江1]
======
key: 及时雨2 value: 宋江2
key: 及时雨1 value: 宋江1

5.TreeMap和HashMap的区别

Map底层结构TreeMapHashMap
底层结构红黑树哈希桶
插入/删除/查找时间复杂度O(log2^N)O(1)
是否有序关于Key有序无序
线程安全不安全不安全
插入/删除/查找区别需要进行元素比较通过哈希函数计算哈希地址
比较与覆写key必须能够比较，否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法
应用场景需要Key有序场景下Key是否有序不关心，需要更高的时间性能

三、集合Set的使用

Set与Map主要的不同有两点：
1、Set是继承自Collection的接口类。
2、Set中只存储了Key。

1.Set集合中常用的方法说明

方法解释
boolean add(E e)添加元素，但重复元素不会被添加成功
void clear()清空集合
boolean contains(Object o)判断 o 是否在集合中
Iterator< E> iterator()返回迭代器
boolean remove(Object o)删除集合中的 o
int size()返回set中元素的个数
boolean isEmpty()检测set是否为空，空返回true，否则返回false
Object[] toArray()将set中的元素转换为数组返回
boolean containsAll(Collection<?> c)集合c中的元素是否在set中全部存在，是返回true，否则返回false
boolean addAll(Collection<? extends E> c)将集合c中的元素添加到set中，可以达到去重的效果

注意：

  1. Set是继承自Collection的一个接口类
  2. Set中只存储了key，并且要求key一定要唯一
  3. Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
  4. Set最大的功能就是对集合中的元素进行去重
  5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
  6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
  7. TreeSet和HashSet的区别
Set底层结构TreeSetHashSet
底层结构红黑树哈希桶
插入/删除/查找时间复杂度O(log2^N)O(1)
是否有序关于Key有序不一定有序
线程安全不安全不安全
插入/删除/查找区别按照红黑树的特性来进行插入和删除1. 先计算key哈希地址 2. 然后进行插入和删除
比较与覆写key必须能够比较，否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法
应用场景需要Key有序场景下Key是否有序不关心，需要更高的时间性能

2.Set集合中方法的详细说明

1.Set中不存在相同的Key，即使调用add方法添加了相同的Key，打印的Set里面也只会含有一个Key值。

public class Test {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("zjr");
        set.add("zjr1");
        set.add("zjr1");
        System.out.println(set);//[zjr, zjr1]
    }
}

2.调用Set集合中的迭代器，返回的类型是Iterator< E>。则迭代器能够打印set里面的元素。

public class Test {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("zjr");
        set.add("zjr1");
        Iterator<String> iterator = set.iterator();
        while(iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

3.调用Set集合的toArray方法，它的返回值类型是Object[]，因为在Java当中数组不能够整体强转，因此只能用Object[]类型的数组去接收。

四、有关Map与Set的基础题

1.有10w个数据，如何找到第一个重复的数据？
思路：因为Set能够去除重复的元素，因此将一个个元素依次添加到Set后，每添加一次前判断是否包含该元素，如果是第一次包含的直接返回该元素。

public static void main5(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 10_0000; i++) {
            list.add(random.nextInt(10000));
        }

        HashSet<Integer> set = new HashSet<>();

        for (int i = 0; i < list.size(); i++) {
            if(set.contains(list.get(i))) {
                System.out.println(list.get(i));
                break;
            }else {
                set.add(list.get(i));
            }
        }
    }

2.有10w个数据，如何去除掉所有重复的数据？
思路：因为Set集合当中不包含重复的元素，并且能够自动去除重复的元素，因此将10w个数据添加到Set集合当中则能够去掉所有重复的数据。

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 10_0000; i++) {
            list.add(random.nextInt(10000));
        }

        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < list.size(); i++) {
            set.add(list.get(i));
        }
        System.out.println(set);
    }

3.有10w个数据，如何统计每个数据出现了多少次？
思路：因为Map集合中能够将每个Key值对应一个Value值，因此利用Map能够记录每个元素出现了多少次。

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 10_0000; i++) {
            list.add(random.nextInt(10000));
        }
        //        数据    次数
        HashMap<Integer,Integer> map = new HashMap<>();
        for (Integer key : list) {
            if(map.get(key) == null) {
                map.put(key,1);
            }else {
                //说明之前存储过
                int count = map.get(key);
                map.put(key,count+1);
            }
        }

        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if(entry.getValue() > 1) {
                System.out.println("重复的数据: "+entry.getKey() +"出现的次数 : "+entry.getValue());
            }
        }
    }

五、有关Map与Set的面试题

1.只出现一次的数字

对应leetcode题

思路：
第一种：跟上面的基础面试题中统计每个数据出现多少次的道理相似，将所有元素用Map记录，所有元素都添加到Map后，则找到Value为1的数字，返回即可。

第二种：跟上面基础面试题中返回第一个出现的元素相似，将每个元素依次添加到Set中，添加前先判断是否有元素已经在Set中，若有则将Set中已有的元素用remove方法删除。最后Set当中只剩一个只出现一次的数字。

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++) {
            if(set.contains(nums[i])) {
                set.remove(nums[i]);
            }else {
                set.add(nums[i]);
            }
        }
        for(Integer a:set) {
            return a;
        }
        return -1;
    }
}

2.复制带随机指针的链表

对应leetcode题

思路：题目要求复制链表中的指针都不应指向原链表中的节点，因此不能直接复制原链表中的结点，否则会指向原链表中的结点。

因此可以利用Map中的每一个Key对应一个Value的原理，第一个结点对应的是复制的新的第一个结点，第二个结点对应的是复制的第二个结点，以此类推。

首先用cur指向第一个结点，当cur不为空，就创建一个结点，将val值复制到结点当中，并且设置Map第一个结点对应的是创建的第一个结点以此类推。这个是第一次遍历原链表。

第二次遍历原链表，目的是将创建的新的结点的next与random域指向与原链表的对应的位置。

如：下图为原链表，则复制的链表也要为是这种结构。

第一次遍历后有Map：

因此第二次遍历原链表时有map.get(cur).next=map.get(cur.next);与map.get(cur).random=map.get(cur.random);，map.get(cur)拿到的是Map中对应的新的结点，map.get(cur.next)拿到的是Map当中cur.next的对应的新的结点。random域也是同样的道理。

代码：

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) {
            return null;
        }
        Node cur = head;
        Map<Node,Node> map = new HashMap<>();
        while(cur!=null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }
        cur=head;
        while(cur!=null) {
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }
}

3.宝石与石头

对应leetcode题

思路：因为给了两个字符串，并且判断石头里面是否有宝石。只需要将石头里面的字符串去重（用到Set集合）并且用计数器记录石头与宝石的字符有多少个是相同的即可。

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        Set<Character> set = new HashSet<>();
        int i=0;
        while(i<jewels.length()) {
            char ch = jewels.charAt(i);
            set.add(ch);
            i++;
        }
        int j=0;
        while(j<stones.length()) {
            char ch = stones.charAt(j);
            if(set.contains(ch)) {
                count++;
            }
            j++;
        }
        return count; 
    }
}

4.坏键盘打字

对应牛客题

< br/>指的是换行。

7_This_is_a_test 与
_hs_s_a_es 对比少了什么

少了7Ti，但是输出的要大写，并且按照先少的顺序打印。

思路：首先将第一个输入的字符串全部变为大写并且转为字符数组存入Set set1集合当中，从头开始遍历第二个输入的字符串，如果set1中没有该字符，则将该字符添加到set2中。set2的设置是避免重复的打印，因此也要判断set2中是否有该字符。set1与set2中都没有该字符则可以打印。

set1中有该字符则说明该键是好的，set2中没有该字符则避免重复的打印。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str1 = scan.nextLine();
        String str2 = scan.nextLine();
        Set<Character> set = new HashSet<>();
        for(char ch:str2.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        Set<Character> set2 = new HashSet<>();
        for(char ch:str1.toUpperCase().toCharArray()) {
            if(!set.contains(ch)&&!set2.contains(ch)) {
                set2.add(ch);
                System.out.print(ch);
            }
        }
    }
}

5.前k个高频单词

对应leetcode题

思路：看到题目，首先想到的是topK问题，又因为找前k个出现次数最多的单词，则创建的是小堆。

观察示例1：如果找前k个次数最多的，并且出现次数相同时，输出的顺序是字母顺序。

观察示例2：如果找前k个次数最多的，并且出现次数不相同时，输出的顺序是出现的次数由高到低。

步骤：
1、首先一定是创建一个Map来记录每个单词出现的次数。再遍历字符串数组在Map中找到对应的Map.Entry<String,Integer>类型创建小堆，当有字符串出现的次数比堆顶多时，堆顶的元素要出堆，而遍历到的字符串的Map.Entry<String,Integer>类型要进堆。

2、小堆的顺序一定是从小到大的排序，而最后输出的是从大到小的排序，并且方法的返回值类型为List< String>，因此我们可以将最后的list倒序存放。

3、而单单比较字符串的出现的次数还不够，因为示例一中提到出现次数相同时要按照首字母的大小顺序输出。因此我们将堆的创建改为：当字符串出现的次数不同时，按照小堆创建堆，则出现次数最少的放在最前面；当字符串比较的出现相同时，按照大堆创建堆，则首字母最大的放在最前面。这种操作的主要原因是最后存放到List< String>当中可以逆序，逆序后能够满足示例1与示例2。

4、因为堆中的元素的类型都是Map.Entry<String,Integer>类型，而方法的返回值是List< String>,因此可以遍历堆中的元素，调用getKey方法获取Map.Entry<String,Integer>中的String类型的数据。因为此时堆是按照出现次数由低到高存放的，首字母由大到小存放的；因此将对应的字符串存入List< String>当中后调用Collections集合中的reverse方法逆置list。

注意：对堆顶元素操作前要判断该堆顶元素是否为空。

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> list = new LinkedList<>();
        if(words==null) {
            return list;
        }
        Map<String,Integer> map = new HashMap<>();
        for (String s:words) {
            if(map.get(s)==null) {
                map.put(s,1);
            }else {
                int count = map.get(s);
                map.put(s,count+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(k, 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()-o2.getValue();
            }
        });
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if (queue.size() < k) {
                queue.offer(entry);
            } else {
                Map.Entry<String, Integer> top = queue.peek();
                if (top != null) {
                    if(top.getValue().compareTo(entry.getValue())==0) {
                        if(top.getKey().compareTo(entry.getKey())>0) {
                            queue.poll();
                            queue.offer(entry);
                        }
                    }else {
                        if(top.getValue()<entry.getValue()) {
                            queue.poll();
                            queue.offer(entry);
                        }
                    }
                }
            }
        }
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = queue.poll();
            if(top!=null) {
                String key = top.getKey();
                list.add(key);
            }
        }
        Collections.reverse(list);
        return list;
    }
}

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/ZJRUIII/article/details/122650868

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com