面试题答案
一键面试set容器插入新元素的时间复杂度及原因：- 时间复杂度：在已有大量数据的
set容器中插入一个新元素的时间复杂度为$O(\log n)$，其中$n$是set容器中元素的个数。 - 原因：
set容器基于红黑树实现，红黑树是一种自平衡的二叉搜索树。红黑树的性质保证了树的高度始终保持在$O(\log n)$级别。插入操作在红黑树中首先需要通过比较找到合适的插入位置，这个查找过程类似于二叉搜索树的查找，时间复杂度为树的高度，即$O(\log n)$。插入新元素后，为了维护红黑树的性质（如节点颜色规则、左右子树高度差等），可能需要进行旋转和颜色调整操作，这些操作的时间复杂度同样是$O(\log n)$。所以总体插入操作的时间复杂度为$O(\log n)$。set的排序原理依赖于红黑树作为二叉搜索树的特性，左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值，这种结构使得插入时能按序找到合适位置。
- 时间复杂度：在已有大量数据的
unordered_set容器插入新元素的时间复杂度及与set的差异原因：- 时间复杂度：在已有大量数据的
unordered_set容器中插入新元素的平均时间复杂度为$O(1)$，最坏情况下时间复杂度为$O(n)$。 - 差异原因：
unordered_set是基于哈希表实现的无序容器。哈希表通过哈希函数将元素映射到不同的桶（bucket）中。理想情况下，哈希函数能将元素均匀分布到各个桶中，插入操作时，先通过哈希函数计算元素的哈希值，直接定位到对应的桶，然后在桶内进行插入（如果桶内采用链表等结构，插入链表头时间复杂度为$O(1)$），所以平均时间复杂度为$O(1)$。然而，当哈希函数设计不合理或者数据分布不均匀时，会导致大量元素哈希到同一个桶中，此时桶内的操作就类似于在链表或其他线性结构中操作，最坏情况下时间复杂度会退化为$O(n)$。与set不同，unordered_set不关心元素的顺序，不基于比较来确定元素位置，而是基于哈希值，所以平均插入效率更高，但存在最坏情况性能问题。
- 时间复杂度：在已有大量数据的