[leetcode] 41 First Missing Poso

题目链接

image.png

给定 一个无序的数组（有正有负），返回数组中不存在的最小正数， 要求
时间复杂度O（n）
空间复杂度O (1)

首先很容易想到空间复杂度为O（n）的解法。
如果input 数组长度为 N， 那么 我们开辟一个 长度为N,初始值为-1的数组 arr。
用来记录 每个整数是否出现过。-1 表示没有出现， 1 表示出现过。
遍历一遍 input 数组， 有符合条件的（值在[1,N]之间）， 就把 arr 对应的位置赋为1.
最后在遍历一遍arr 数组， 找到第一个为-1 的， 就是 missing的数。

#include <vector>
#include <iostream>

using namespace std;


class Solution {
public:
    int firstMissingPositive(vector<int>& nums) 
    {
        if(nums.empty())
            return 1;
        
        vector<int> arr(nums.size(),-1);

        for(int i =0; i < nums.size(); i++)
        {
            if(nums[i] > 0 && nums[i] <= nums.size()){
                arr[nums[i]-1] = 1;
            }
        }  
        
        for(int i = 0; i < arr.size(); i++)
        {
            if(arr[i] == -1){
                return i+1;
            }
        }
        return nums.size()+1;
        
    }
};

如果不开辟空间， 那就只能在原数组上修改了。
这里我们用 取负 ， 来表示该下标下对应整数已经出现过。
这里对每一个符合条件的（绝对值在[1, N]）内的 ， 将 对应index 的数字变为负数，表示该index 对应的数已经出现过了。

当然， 因为这里用取负来表示 已经出现过该点， 所以一开始要预先处理一下 不符合条件的数（ <= 0 || > N）, 将他们都变为大于 N的正数。

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        
        for(int i =0 ; i < nums.size(); i++){
            if(nums[i] <= 0 || nums[i] > nums.size()){
                nums[i] = nums.size() +1;
            }
        }


        for(int i = 0; i < nums.size(); i++){
            if(abs(nums[i]) > 0 && abs(nums[i]) <= nums.size()){
                if(nums[abs(nums[i])  -1] >0)
                    nums[abs(nums[i]) -1] *=-1;
            }
        }


        for(int i = 0; i < nums.size();i++){
            if(nums[i] > 0 )
                return i+1; 
        }
        return nums.size()+1;
        
    }
};

image.png