LeetCode-895. 最大频率栈以及HashMap的存值取值操作

题目描述

设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
实现 FreqStack 类:
FreqStack() 构造一个空的堆栈。
void push(int val) 将一个整数val压入栈顶。
int pop() 删除并返回堆栈中出现频率最高的元素。
如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。

解题思路

实现使用一个变量maxFreq更新每次操作的最大频次

使用哈希表和栈，建立一个存储val和其对应出现频次的哈希表，在建立一个频次key和当前频次出现有哪些元素value使用栈对出现的频次的元素保存的哈希表

代码

class FreqStack {
    // key是val，value是val对应的频次
    private Map<Integer,Integer> freq;
    // key 存储频次，value是val入队的队列
    private Map<Integer,Deque<Integer>> group;
    private int maxFreq;
    public FreqStack() {
        freq = new HashMap<Integer,Integer>();
        group = new HashMap<Integer,Deque<Integer>>();
        maxFreq = 0;
    }
    
    public void push(int val) {
        // freq.get(val) 记录的是val的频率
        freq.put(val,freq.getOrDefault(val,0)+1);
        // group.get(频次) 记录的是 频次对应出现的元素，putIfAbsent是key为空就
        group.putIfAbsent(freq.get(val), new ArrayDeque<Integer>());
        group.get(freq.get(val)).push(val);
        // maxFreq 标记每次最大的频次
        maxFreq = Math.max(maxFreq,freq.get(val));
    }
    
    public int pop() {
        int val = group.get(maxFreq).pop();
        freq.put(val,freq.get(val)-1);
        // 最大频次的队列不为空，最大频率就始终是key
        if (group.get(maxFreq).isEmpty()) {
            maxFreq--;
        }
        return val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

思考和普及

HashMap类是java.util包下，HashMap的类继承了抽象Map的抽象类，实现Map接口，可以克隆复制的接口，序列化接口

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable
1

HashMap 的 putIfAbsent()，方法会先判断指定的键 key 是否存在，不存在则将键值对插入到 HashMap 中。如果所指定的 key 不在 HashMap 中存在，则返回 null

注意，如果指定 key 之前已经和一个 null 值相关联了 ，则该方法也返回 null，因为 HashMap 的key允许有且仅有一个为 null

    public V getOrDefault(Object key, V defaultValue) {
        Node e;
        return (e = this.getNode(hash(key), key)) == null ? defaultValue : e.value;
    }

    public V putIfAbsent(K key, V value) {
        return this.putVal(hash(key), key, value, true, true);
    }
1
2
3
4
5
6
7
8

HashMap的哈希函数的实现，

    static final int hash(Object key) {
        int h;
        return key == null ? 0 : (h = key.hashCode()) ^ h >>> 16;
    }
1
2
3
4

HashMap的put方法

首次扩容，判断数组是否为空，如果数组为空，则进行第一次扩容

在自定义数组容量公式是 容量大小 = 需要的空间 / 0.75 + 1

第二步，计算索引，通过上面的哈希函数，计算键值对在数组中的索引

第三步，插入元素，如果当前位置元素为null，直接插入；如果当前位置元素不为null，并且key已经存在，则直接覆盖掉value；如果当前位置元素不为null，并且key不存在，就将数据链接到链表的末尾；若链表的长度达到8，链表就转化为红黑树，并且将数据插入到树中

第四步，再次扩容，如果数组元素的个数大于threshold，就再次进行扩容

    private static final long serialVersionUID = 362498820763181265L;
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    static final int MAXIMUM_CAPACITY = 1073741824;
    static final float DEFAULT_LOAD_FACTOR = 0.75F;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    transient Node<K, V>[] table;
    transient Set<Map.Entry<K, V>> entrySet;
    transient int size;
    transient int modCount;
    int threshold;
    final float loadFactor;
1
2
3
4
5
6
7
8
9
10
11
12
13

HashMap的put方法，调用了putVal方法

    public V put(K key, V value) {
        return this.putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node[] tab;
        int n;
        if ((tab = this.table) == null || (n = tab.length) == 0) {
            n = (tab = this.resize()).length;
        }

        Object p;
        int i;
        if ((p = tab[i = n - 1 & hash]) == null) {
            tab[i] = this.newNode(hash, key, value, (Node)null);
        } else {
            Object e;
            Object k;
            if (((Node)p).hash == hash && ((k = ((Node)p).key) == key || key != null && key.equals(k))) {
                e = p;
            } else if (p instanceof TreeNode) {
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            } else {
                int binCount = 0;

                while(true) {
                    if ((e = ((Node)p).next) == null) {
                        ((Node)p).next = this.newNode(hash, key, value, (Node)null);
                        if (binCount >= 7) {
                            this.treeifyBin(tab, hash);
                        }
                        break;
                    }

                    if (((Node)e).hash == hash && ((k = ((Node)e).key) == key || key != null && key.equals(k))) {
                        break;
                    }

                    p = e;
                    ++binCount;
                }
            }

            if (e != null) {
                V oldValue = ((Node)e).value;
                if (!onlyIfAbsent || oldValue == null) {
                    ((Node)e).value = value;
                }

                this.afterNodeAccess((Node)e);
                return oldValue;
            }
        }

        ++this.modCount;
        if (++this.size > this.threshold) {
            this.resize();
        }

        this.afterNodeInsertion(evict);
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

HashMap的get操作，根据传入的key查询到哈希函数操作之后的节点，判断这个节点是否为null，为空返回null，不为空返回节点值

    public V get(Object key) {
        Node e;
        return (e = this.getNode(hash(key), key)) == null ? null : e.value;
    }
    final Node<K, V> getNode(int hash, Object key) {
        Node[] tab;
        Node first;
        int n;
        if ((tab = this.table) != null && (n = tab.length) > 0 && (first = tab[n - 1 & hash]) != null) {
            Object k;
            if (first.hash == hash && ((k = first.key) == key || key != null && key.equals(k))) {
                return first;
            }

            Node e;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode) {
                    return ((TreeNode)first).getTreeNode(hash, key);
                }

                do {
                    if (e.hash == hash && ((k = e.key) == key || key != null && key.equals(k))) {
                        return e;
                    }
                } while((e = e.next) != null);
            }
        }

        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30