LeetCode 缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:
输入: [1,2,0]
输出: 3

示例 2:
输入: [3,4,-1,1]
输出: 2

示例 3:
输入: [7,8,9,11,12]
输出: 1

说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

思路分析：解此题需要在序列中确定缺失的最小的正整数，我想到了两种方法，第一种是利用关联容器map将出现的正数与其出现的次数进行关联，然后用for从1到+无穷进行判断存在性，时间复杂度为o(n)，时间复杂度为o(n),(超出了题目的限制。。。)；第二种是将nums容器利用算法库中sort算法进行排序，然后找出第一个最小的正数的位置，最后用for从1到+无穷进行判断存在性，时间复杂度为o(log n)最差的情况也会达到o(n)，空间复杂度为常数。
下面将给出第二种，排序+for 的算法实现。

int firstMissingPositive(vector<int>& nums) {
	int numsSize = nums.size();
	if (numsSize == 0){
		return 1;
	}
	sort(nums.begin(), nums.end());
	int index = -1;
	while (index + 1 < numsSize && nums[index + 1] <= 0){
		++index;
	}
	index += 1;//定位到第一个正数的位置
	for (int i = 1;; ++i){
		if (index < numsSize && nums[index] == i){
			++index;//如果此数存在，则index需要自增
			continue;
		}
		else {
			return i;
		}
	}
}

LeetCode 缺失的第一个正数
这道题算法存在缺陷，请思考一下！
我们先将不通过的示例进行排序，然后模拟执行。

所以问题在于for循环中index的自增未解决nums容器中的重复元素的问题。
修改之后的代码：

class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		int numsSize = nums.size();
		if (numsSize == 0){
			return 1;
		}
		sort(nums.begin(), nums.end());//排序，方便后期寻找
		int index = -1;
		while (index + 1 < numsSize && nums[index + 1] <= 0){
			++index;
		}
		index += 1;//定位到第一个正数的位置
		for (int i = 1;; ++i){
			if (index < numsSize && nums[index] == i){
				while (index < numsSize && nums[index] == i){//跳过重复元素
					++index;
				}
				continue;
			}
			else {
				return i;
			}
		}
	}
};

LeetCode 缺失的第一个正数
虽然是挺快的，但是此算法会带来一些副作用，比如在排序的时候，将会改变原容器nums的顺序。
对于第一种算法出现的空间超限问题，可以将map容器修改为一个比较大的常数级别的数组，采取计数排序的策略进行优化。

class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		int numsSize = nums.size();
		bool flag[100] = { false };//用于标记i是否存在
		for (int i = 0; i < numsSize; i++) 
			if (nums[i] > 0)//正数进行标记
				flag[nums[i]] = true;
		int index = 1;
		while (flag[index]){//定位index为第一个不存在的正整数
			++index；
		}
		return index;
	}
};

LeetCode 缺失的第一个正数

相关推荐