题意概述

给定一个无重复的整数数组
找出其中没有出现的最小正整数

方法一：哈希

思路与具体做法

首先遍历整个数组，并用unordered_map标记该数字已出现
然后从1遍历到n，并在unordered_map查找该值是否出现，未出现则直接返回
若长度为n的数组里n个数字都出现了，则第n+1个数字一个未出现

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
    	int n=nums.size();
    	unordered_map<int,int>m;
        for(int i=0;i<n;i++){//统计每个数字出现的次数
        	m[nums[i]]++;
		} 
        for(int i=1;i<=n;i++){//出现次数为0的直接返回
        	if(m[i]==0)return i;
		}
		return n+1;
    }
};

时间复杂度和空间复杂度分析

时间复杂度： $O (n)$ ，遍历了一次长度为n的数组和枚举一次长度n-1的数
空间复杂度： $O (n)$ ，建立了长度为n的哈希表

方法二：排序后直接遍历

思路与具体做法

对输入的数组进行排序
遍历一次数组，不是正整数的数则统计其个数，是正整数则按序从1开始往后逐次比较，比较不成功的则直接返回
最后若能遍历完数组，说明这是一串从1开始连续的数组，则返回所有正整数数目加一即可

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n=nums.size(),cn=0,cn2=0;
        for(int i=0;i<n;i++){
            if(nums[i]<=0)cn++;//不是正整数的数则统计其个数
            else if(nums[i]!=++cn2)return cn2;//是正整数则按序从1开始往后逐次比较，比较不成功的则直接返回
        }
        return n-cn+1;
    }
};

时间复杂度和空间复杂度分析

时间复杂度： $O(n\log_{2}{n} )$ ，排序耗时 $O(n\log_{2}{n} )$ ，遍历数组 $O (n)$
空间复杂度： $O (1)$ ，仅定义了几个整形变量

方法三：二分查找

思路与具体做法

对输入的数组进行排序
接着从1到遍历n，对遍历到的数字在输入数组中进行二分查找
最后若从1到遍历n，这n个正整数都存在，则正整数n+1一定不存在

class Solution {
public:
	int binarysearch(vector<int>& nums,int t){//在给定区间内二分查找
		int l=0,r=nums.size()-1;
		while(l<=r){
			int mid=l+(r-l)/2;
			if(nums[mid]==t)return mid;
			else if(nums[mid]<t)l=mid+1;
			else r=mid-1; 
		}
        return -1;
	}
    int minNumberDisappeared(vector<int>& nums) {
	    int n=nums.size();
	    sort(nums.begin(),nums.end());//排序
		for(int i=1;i<=n;i++){//对1~n所有元素依次使用二分查找
			if(binarysearch(nums,i)==-1)return i;//找不到说明出现次数为1
		} 
		return n+1;//若从1到遍历n，这n个正整数都存在，则正整数n+1一定不存在
    }
};

时间复杂度和空间复杂度分析

时间复杂度： $O(n\log_{2}{n} )$ ，排序耗时 $O(n\log_{2}{n} )$ ，二分查找每一步 $O(\log_{2}{n} )$
空间复杂度： $O (1)$ ，仅定义了几个整形变量

题解 | #缺失的第一个正整数#

题意概述

方法一：哈希

思路与具体做法

时间复杂度和空间复杂度分析

方法二：排序后直接遍历

思路与具体做法

时间复杂度和空间复杂度分析

方法三：二分查找

思路与具体做法

时间复杂度和空间复杂度分析