面试题：C++ vector优化基于值查询时间复杂度

优化方案：
- 可以使用哈希表（unordered_map）来辅助查询。哈希表能够提供平均 $O(1)$ 的查询时间复杂度。具体做法是，在插入元素到 vector 的同时，将元素值作为键，其在 vector 中的索引作为值，插入到 unordered_map 中。这样，当需要基于值查询时，直接在哈希表中查询即可。
代码实现：

#include <iostream>
#include <vector>
#include <unordered_map>

class OptimizedVector {
public:
    void push_back(int val) {
        data.push_back(val);
        indexMap[val] = data.size() - 1;
    }

    int findIndex(int val) {
        auto it = indexMap.find(val);
        if (it != indexMap.end()) {
            return it->second;
        }
        return -1; // 表示未找到
    }

private:
    std::vector<int> data;
    std::unordered_map<int, int> indexMap;
};

优化后的时间复杂度：
- 插入操作：在 vector 中插入元素的时间复杂度为 $O(1)$（平均情况，不考虑扩容），在 unordered_map 中插入元素的时间复杂度也是 $O(1)$（平均情况），所以整体插入操作的平均时间复杂度为 $O(1)$。
- 查询操作：在 unordered_map 中查询元素的平均时间复杂度为 $O(1)$，因此基于值查询的平均时间复杂度从原来 vector 直接查询的 $O(n)$ 降低到了 $O(1)$。之所以能达到 $O(1)$ 的平均时间复杂度，是因为哈希表通过哈希函数将键映射到一个桶（bucket）中，理想情况下，每个桶中的元素数量很少，平均查询时间接近常数时间。但在最坏情况下，哈希表可能会退化为链表，查询时间复杂度会变为 $O(n)$。

面试题：C++ vector优化基于值查询时间复杂度

知识考点

面试题答案