leetcode:First Missing Positive

一、题目

给出一个未排序的数组，找出第一个丢失的正整数，

注：算法是O(n)的时间和常量的空间

二、分析

思路一：

2、如果不符合1则向右移动索引，直到完成；

4、如果元素全部符合，则返回n+1;

class Solution {public:int firstMissingPositive(int A[], int n) {int i = 0;while(i!=n){if(A[i]>0&&A[i]!=A[A[i]-1]&&A[i]<=n){swap(A[i],A[A[i]-1]);}elsei++;//直到第一个符合或者无效跳过}for (int i = 0; i < n; ++i){if(A[i] != i+1)return i+1;}return n+1;}int swap(int &x,int &y){int temp = x;x = y;y = temp;}};

思路二：

1、排序，，从小到大;

3、如果全部符合，则返回k+1;

class Solution {public:int firstMissingPositive(int A[], int n) {if(n == 0) return 1;int k = 0;sort(A,A+n);for (int i = 0; i < n; ++i){if(A[i]>0&&A[i]!=A[i-1]){k++;if (A[i] != k)return k;}}return k+1;}};

前有阻碍，奋力把它冲开，运用炙热的激-情，