First Missing Positive--LeetCode

刺骨的言语ヽ痛彻心扉 2022-08-07 11:57 11阅读 0赞

# 题目： #

Given an unsorted integer array, find the first missing positive integer.

For example,  
Given `[1,2,0]` return `3`,  
and `[3,4,-1,1]` return `2`.

Your algorithm should run in O(n) time and uses constant space.

思路：我觉得题意中找到第一个消失的整数，是指当前数组中第一个消失的整数，可以使用hash表

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    
    int FirstMissingPositive(vector<int>& vec)
    {
    	vector<int> hash(vec.size(),0);
    	int min=vec[0];
    	int i,j;
    	for(i=0;i<vec.size();i++)
    		if(vec[i]>0 && vec[i] <min)
    			min = vec[i];
    	for(i=0;i<vec.size();i++)
    	{
    		if(vec[i]>0)
    			hash[vec[i]-min] =1;
    	}	
    	
    	for(i=0;i<hash.size();i++)
    		if(hash[i] ==1)
    			break;
    	for(;i<hash.size();i++)
    		if(hash[i] == 0)
    			return i+min;
    	return i+min-1;
    }
    
    int main()
    {
    	int array[]={3,4,-1,1};
    	vector<int> vec(array,array+sizeof(array)/sizeof(int));
    	cout<<FirstMissingPositive(vec);
    	return 0;
    }

这道题要求用线性时间和常量空间，思想借鉴到了Counting sort中的方法，不了解的朋友可以参见[Counting sort - Wikipedia][]。既然不能用额外空间，那就只有利用数组本身，跟Counting sort一样，利用数组的index来作为数字本身的索引，把正数按照递增顺序依次放到数组中。即让A\[0\]=1, A\[1\]=2, A\[2\]=3, ... , 这样一来，最后如果哪个数组元素违反了A\[i\]=i+1即说明i+1就是我们要求的第一个缺失的正数。对于那些不在范围内的数字，我们可以直接跳过，比如说负数，0，或者超过数组长度的正数，这些都不会是我们的答案。代码如下：

public int firstMissingPositive(int[] A) {  
            if(A==null || A.length==0)  
            {  
                return 1;  
            }  
            for(int i=0;i<A.length;i++)  
            {  
                if(A[i]<=A.length && A[i]>0 && A[A[i]-1]!=A[i])  
                {  
                    int temp = A[A[i]-1];  
                    A[A[i]-1] = A[i];  
                    A[i] = temp;  
                    i--;  
                }  
            }  
            for(int i=0;i<A.length;i++)  
            {  
                if(A[i]!=i+1)  
                    return i+1;  
            }  
            return A.length+1;  
        }

ps:题目要求是找出第一个没有的整数，我们可以这么思考，首先找出整个数组中负数的个数，然后我们就知道剩下的正数的个数，同时记录数组中最小的正数，那么我们就开始记录，开始索引，我们使用hash来记录，但是记录的时候需要注意，现在我们已经知道正数的个数，然后发现正数时，如果正数的大小大于剩余正数的个数，那么就没必要插入了，遍历完成以后，值需要从头开始查看，hash表中的某一个位置没有数值，那么找到的第一个不存在的元素就是缺失的元素。

[Counting sort - Wikipedia]: http://en.wikipedia.org/wiki/Counting_sort