面试题库 › 算法 / 大模型 › O(1) 时间插入、删除和获取随机元素(LeetCode 380)

O(1) 时间插入、删除和获取随机元素(LeetCode 380)

难度 ★★☆在 2 场真实面经中被问到 方向:算法 / 大模型考点:数据结构设计

哪些公司问过

字节跳动2

常见岗位:推荐搜索广告、Java 后端

答案要点

  1. 动态数组存元素支持O(1)随机访问,哈希表存值到下标的映射
  2. insert:已存在返回false,否则尾插并记录下标
  3. remove:用末尾元素覆盖被删位置并更新其下标,再弹出末尾、删除映射
  4. getRandom:在[0, size)内取随机下标,等概率返回
  5. 三个操作平均O(1),空间O(n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题