Leetcode排序题中缓存/记忆化为何反而增加运行耗时？

1. 哈希表的额外开销远超计算收益 #

unordered_map的查找、插入操作并非无成本：每次操作需要计算键的哈希值、处理桶的链表结构，甚至可能触发内存分配。而计算数字的映射值本身开销极低——遍历数字的每一位（最多10位）做映射的CPU指令数，可能比哈希表的一次查找还要少。如果数组中重复元素不多，缓存带来的“避免重复计算”收益完全抵不上哈希表的额外开销，反而会因为多了哈希操作拖慢速度。

2. std::sort比较器的调用特性放大了开销 #

std::sort的比较次数是O(n log n)量级。无缓存版每次比较时直接计算映射值，而缓存版每次比较都要先查哈希表：如果元素没缓存过，还要额外执行插入操作。相当于每次比较的常数时间被拉长，最终总耗时反而更高。

3. 缓存命中率不足的情况 #

如果测试用例中数组的重复元素极少，缓存几乎没有命中机会。这时缓存版的逻辑变成“查哈希表→没找到→计算映射值→插入哈希表”，比无缓存版多了两步哈希操作，自然耗时翻倍。

更优的实现方案 #

与其用哈希表做动态缓存，不如提前预计算所有元素的映射值：

• 遍历数组，为每个元素计算一次映射值，将原元素和映射值存成一对（比如vector<pair<int, int>>）
• 对这个pair数组按照映射值排序
• 最后提取排序后的原元素组成结果数组

这种方案的总开销是O(n*k + n log n)（k为数字位数），既避免了哈希表的额外开销，也彻底消除了重复计算。示例代码大致如下：

vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
    vector<pair<int, int>> num_map;
    for (int num : nums) {
        int mapped = 0;
        int tmp = num;
        if (tmp == 0) {
            mapped = mapping[0];
        } else {
            while (tmp > 0) {
                mapped = mapped * 10 + mapping[tmp % 10];
                tmp /= 10;
            }
        }
        num_map.emplace_back(mapped, num);
    }
    sort(num_map.begin(), num_map.end());
    vector<int> res;
    for (auto& p : num_map) {
        res.push_back(p.second);
    }
    return res;
}

内容的提问来源于stack exchange，提问作者Divij Jain