【LeetCode 41】缺失的第一个正数

【题解】

先明确一点假设给的数字有n个。
那么最后的答案最情况下就是n+1
首先我们先判断一下所给的数组里面有没有1
如果没有直接返回1
否则。
把数组中所有的范围超过n或者小于1的数字全都改成数字1
然后扫描一遍整个数组。
for(int i = 0;i

【代码】

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

        bool ok = false;

        for (int x:nums){

            if (x==1){

                ok = true;

            }

        }

        if (!ok) return 1;

        int len = nums.size();

        for (int i = 0;i < len;i++){

            if (nums[i]>len || nums[i]<1){

                nums[i] = 1;

            }

        }

        for (int i = 0;i < len;i++){

            int x = nums[i];

            if (x<0){

                x=-x;

            }

            nums[x-1]=-abs(nums[x-1]);

        }

        for (int i = 0;i < len;i++)

            if (nums[i]>0)

                return i+1;

        return len+1;

    }

};

巴特西

【LeetCode 41】缺失的第一个正数

最新文章

热门文章