C++朝花夕拾
从一道 groupAnagrams 题谈 STL 容器、哈希与字符串优化 起点:一段"看起来聪明但其实买椟还珠"的代码 // 用 map<int,int> 统计字符频次,再把这个 map 作为外层 map 的 key map<map<int,int>, int> cache; 直觉上"用频次代替排序"是好思路(O(n) vs O(n log n)),但 容器选择把这个优势全部抹掉 。 一、 map 的 key 不走哈希 第一个常见误解: std::map<K, V> 是 红黑树 + operator< ,不是哈希表。 std::map 查找:O(log N) 次 key 之间的字典序比较 std::unordered_map 查找:平均 O(1),需要 std::hash<K> 把 map<int,int> 当 key,每次 find 是 O(log N) 次树遍历比较 ,每次比较还要遍历内层 map 的所有 pair——常数极差。 二、复杂度分析要分清"渐近"和"常数" 渐近最优 (asymptotically optimal)= 在大 O 意义上达到问题下界,再优化只能改善常数。 groupAnagrams 在 σ=26(小写字母)假设下: 方案 key 构造 key 比较 map<map<int,int>, int> O(k) O(σ)=O(1) 排序 string O(k log k) O(k) array<int,26> O(k) O(σ)=O(1) 关键认知 : σ 视为常数时,方案一和方案三 渐近同阶 ,差距全在常数(堆分配 vs 栈数组) σ 视为变量时,三者才有渐近差距 "渐近最优"和"工程最优"不是一回事——常数因子在实际系统里可能差几十倍 三、k 的规模决定方案选型 k 范围 推荐 理由 k ≤ ~20 排序 string 落在 ...