腾讯秋招提前批AI Lab一面面试题
nums[1] != 2
就返回缺失的2class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int size = nums.size();
// 1.遇到与索引+1不同的数就置换,如[3,4,-1,1],其中nums[0] = 3 ≠ 0 + 1, 则swap(nums[0], nums[nums[0] - 1])=>swap(nums[0], nums[2])
for (int i = 0; i < size; i++)
while (nums[i] > 0 && nums[i] < size && nums[i] != nums[nums[i] - 1]) // 特别注意此处防止出现[1,1]导致的死循环
swap(nums[i], nums[nums[i] - 1]);
// 2.只要找到nums[i] != i + 1,就说明缺少的正整数是i + 1
for (int i = 0; i < size; i++)
if (nums[i] != i + 1) return i + 1;
return size + 1;
}
};