来单纯技术讨论一下好了
其实 Visit 也不用限制一定要用 HashMap/HashSet 做
Leetcode 上很多题目的 nodes tag 都是连续的数字或英文字母
这个时候用一般的 Array 效能就会比 HashMap/HashSet 好非常多:
1. 不需动态分配内存(感谢一楼提醒)
2. 不需进行 Hash 运算
但也正如同大多数大大所说
一般人的想像场景不会是连续的标签
在 nodes tag 都不连续的情况下
例如:1, 100, 10000, 1000000, 100000000
这个时候用 Array 就是低能儿了
个人浅见如上
如有错误还请各位大大指正
补充 peter98 与 NTHUlagka 底下关于 Hash 的讨论(小弟对于 C++ 只能算是略懂,如
果错误就再麻烦指正了):
1. 就 C++ Standard Library 对于 HashMap/HashSet 的实作,一开始会先分配一定数量
的 buckets,后续如果超过 loading factor(默认 1.0),再动态增加(std::vecotor
的实作上
一般是加倍)。
2. 关于 Exponential Backoff 与 Bloom Filters 等其他技术,目前尚未实作于 Standa
rd Library 里,所以有需求的话要自行实作。
3. Bloom Filters 可以解放传统 HashSet 储存空间带来的限制,原理很简单,如果不太
清楚请中文维基就可以轻松看懂(一般大学的分布式系统课程也都会教到)。