*LeetCode 41. First Missing Positive 思维题

本文主要是介绍*LeetCode 41. First Missing Positive 思维题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/first-missing-positive/

如果是只缺一个数的话，好说，就是求和， 然后n*(n+1)/2 -sum  就是缺的数字

但是，，，这道题，这样的数据也是要求有正确结果的：

3

1 4 5

这类题最终要的是：找到一些性质

这个题需要理解的性质是，假设缺的数是ans，那么他应该出现在下标为ans-1 的位置

而且下标为0 ~ ans-2都是符合nums[i] = i+1

有两个trick:

（1）如果现在的序列已经是，比如数组大小是3, 1-3都有，那么应该返回数组长度+1

（2）有重复的数字的时候，这个时候可能死循环，比如2应该放到第1个位置，那么再遇到一个2，就要跟第一个位置的2交换了，就这样死循环，，，，

所以无效的交换不要做

测试数据：
2

1 1

应该返回2

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>using namespace std;class Solution {
public:int firstMissingPositive(vector<int>& nums) {int ptr=0;while(ptr<nums.size()) {if(nums[ptr] == ptr+1 || nums[ptr]<=0 || nums[ptr]>=nums.size() || nums[ptr] == nums[ nums[ptr]-1 ]) ptr++;else {//cout << nums[ptr] << " , " << nums[ nums[ptr]-1 ] << endl;swap(nums[ptr], nums[ nums[ptr]-1 ]);}}for(int i=0;i<nums.size();i++)if(nums[i] != i+1)return i+1;return nums.size()+1;}
};int main() {int n,in;while(cin >> n) {vector<int> ivec;for(int i=0;i<n; i++) {cin >> in;ivec.push_back(in);}Solution s;cout << s.firstMissingPositive(ivec) << endl;}return 0;}

这篇关于*LeetCode 41. First Missing Positive 思维题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---