Leetcode|索引置换|41. 缺失的第一个正数

腾讯秋招提前批AI Lab一面面试题

1 原地数组索引置换

• [3, 4, -1, 1] => [1, -1, 3, 4]，这样遍历到nums[1] != 2就返回缺失的2

代码语言：javascript复制

class 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;
    }
};

遍历 数组 索引 腾讯

0 人点赞