面试题库 › C++ / 后端 › 缺失的第一个正整数(LeetCode 41)

缺失的第一个正整数(LeetCode 41)

难度 ★★★在 3 场真实面经中被问到 方向:C++ / 后端考点:数组与字符串

哪些公司问过

字节跳动1快手1拼多多1

常见岗位:C++ 后端、Java 后端、C/C++ 软件开发

答案要点

  1. 答案一定在 1 到 n+1 之间,只需处理值在 [1, n] 的元素
  2. 原地哈希:把值 v 交换到下标 v-1,交换条件要判断目标位置值不等于 v
  3. 第二遍找第一个 nums[i] 不等于 i+1 的位置,返回 i+1,都匹配返回 n+1
  4. 每次交换至少让一个数归位,总交换次数不超过 n,时间 O(n)、空间 O(1)

易错点

面试官常见追问

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

相关面试题