Leetcode 41. First Missing Positive (cpp)

题目

解法1：

首先是时间复杂度O(1)，空间复杂度O(n)的解法。关键在于答案一定会在1~n+1中产生，n为数组长度。那么先保存出现过的num，然后遍历1到n+1，找第一个没有出现的即可

class Solution {
    
public:int firstMissingPositive(vector<int>& nums) {
    unordered_map<int,int> seen;for(int i=0;i<nums.size();i++){
    seen[nums[i]] = 1;}for(int i=1;i<=nums.size()+1;i++){
    if(seen.find(i) == seen.end()){
    return i;}}return 0;}
};

解法2：

优化空间复杂度到O(1)，以数组中元素的正负为信息，储存这个元素的index的数字是否出现过。比如[1,-2,-3]表示1,2出现过，0没有出现过。需要对小于0和大于n+1的元素进行预处理，因为他们是没用的。虽然这道题目没什么意思，但是这种思想还是值得借鉴，利用index作为hash key，负号作为hash value。因为修改符号并不修改数字的绝对值，所以原来的数字即使被修改符号也能被retrieve回来。

class Solution {
    
public:int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();// replace all the 0, negative numbers and numbers > n to n+1for(int i=0;i<n;i++){
    if(nums[i]<=0 || nums[i]>n){
    nums[i] = n + 1;}}for(int i=0;i<n;i++){
    int num = abs(nums[i]);// skip all the invalid elementif(num>n){
    continue;}// change to zero indexnum -= 1;// change the number at num position to be negative, indicate the number num has appearedif(nums[num] > 0){
     // avoid dould negative operation due to duplicatesnums[num] *= -1;} }// look for the first positive number, the index of the first positive number is the first missing positive numberfor(int i=0;i<n;i++){
    if(nums[i] > 0){
    return i+1;}}return n+1;}
};