Java教程

41. 缺失的第一个正数

本文主要是介绍41. 缺失的第一个正数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 

示例 1:

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

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

输入:nums = [7,8,9,11,12]
输出:1
 

提示:

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

 

 

#include<iostream>
#include<stack>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
/*
遍历一次数组查当前下标是否和值对应,如果不对应那这个下标就是答案,
否则遍历完都没出现那么答案就是数组长度加1。
*/


class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int n = nums.size();
		int res = 1;
		for (int i = 0; i < n; ++i)
		{
			if (nums[i]>0)
			{
				if (nums[i] == res)
				{
					res++;
				}
				else if (nums[i]>res)
				{
					break;
				}
			}

		}
		return res;
	}

};

int main()
{
	int a[1000];
	int x;
	int i = 0;
	vector<int> vec;
	int target;
	while (cin >> a[i])
	{
		vec.push_back(a[i]);
		i++;//注意这里i++对输出结果的影响
		x = cin.get();
		if (x == '\n')
			break;

	}
	int ans = Solution().firstMissingPositive(vec);
	cout << ans << endl;
	system("pause");
	return 0;
}

  

 

这篇关于41. 缺失的第一个正数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!