数据结构：哈希表与堆

数据结构类面试问题的三种考法

考法1：问某种数据结构的基本原理，并要求实现
例题：说一下Hash的原理并实现一个Hash表

考法2：使用某种数据结构完成事情
例题：归并K个有序数组

考法3：多个数据结构配合在一起使用，提供一些特定的功能
例题：LRU

Set / HashSet

特点：数据无重复，且无序

应用：去重，快速查找某数据是否存在

应用：分类计数，存储且快速找到key所对应的value

链表：

dummy点的作用:

dummy点为头结点的前一个节点

如果没有dummy点，头结点就没有前一个节点

而其他点都有前一个节点，所以需要分类讨论，逻辑复杂

数据结构设计题

常见解决线性表缺陷的方法

链表

迅速找到链表中要被删的元素：

• 用HashMap

  如LRU中，keyToPrev

数组

ArrayList插入和删除加速，如果不关心顺序：

• 插入只插到末尾O1

  （如堆的底层实现）

• 删除中间元素时，把中间元素用末尾元素覆盖，然后删掉末尾O1

  （如堆的底层实现）

设计LRU Cache

映射

LinkedList

HashMap：keyToPrev

顺序非常重要，

有LinkedHashMap（Order），也可以直接用这个

堆

第n个丑数

离线算法 vs 在线算法

普通算法问题，数据结构设计类问题

数据给定，数据流问题

一次输入输出，多次输入和输出

离线找到最小的k个元素

时空复杂度最低的方法是：最大堆NlogK（或者快速选择平均On但最差On2）

在线找到最大的k个元素

最大的k元素用小堆，最小的k元素用大堆，

数据结构考点