LeetCode
LeetCode copied to clipboard
Published
20 hours ago •
ylqi007
ylqi007
题目归类
- [ ] 206. Reverse Linked List
- [ ] 92. Reverse Linked List II
- [ ] 25. Reverse Nodes in k-Group
- Solution of 25 is based on the solution of 92
Data Structure Design
这两题考查我们对于实现哈希表，有哪些方法，分别有什么利弊？ 实现哈希表的原理，其实我们会遇到一个抉择，那就是时间和空间的取舍。
实现方式有两种：
- 超大数组：不考虑空间复杂度，创建超大数组，每个数都能单独存入，且不会位置冲突。
- 链地址法：空间/时间的最佳实践，基于数组实现，并且通过一个 hash 函数生成一个对应的索引，当多个数索引一致的时候，再处理冲突问题，一般我们使用链地址法解决冲突。
为了实现哈希集合这一数据结构，有以下几个关键问题需要解决：
- 哈希函数：能够将集合中任意可能的元素映射到一个固定范围的整数值，并将该元素存储到整数值对应的地址上。
- 冲突处理：由于不同元素可能映射到相同的整数值，因此需要在整数值出现「冲突」时，需要进行冲突处理。总的来说，有以下几种策略解决冲突：
- 链地址法：为每个哈希值维护一个链表，并将具有相同哈希值的元素都放入这一链表当中。
- 开放地址法：当发现哈希值 h 处产生冲突时，根据某种策略，从 h 出发找到下一个不冲突的位置。例如，一种最简单的策略是，不断地检查 h+1,h+2,h+3,… 这些整数对应的位置。
- 再哈希法：当发现哈希冲突后，使用另一个哈希函数产生一个新的地址。 扩容：当哈希表元素过多时，冲突的概率将越来越大，而在哈希表中查询一个元素的效率也会越来越低。因此，需要开辟一块更大的空间，来缓解哈希表中发生的冲突。
以上内容读者可以自行翻阅数据结构的教材，本题解不再阐述，而是直接给出一个最简单的哈希表实现。
Reference
- 御三五: https://leetcode.cn/problems/design-hashmap/solutions/654720/wu-tu-guan-fang-tui-jian-ti-jie-she-ji-h-guuw/
- 力扣官方题解: 设计哈希集合
Top K
Method 1: PriorityQueue Method 2: Bucket Sort Method 3: QuickSelect