41. First Missing Positive-白红宇

41. First Missing Positive

阅读量：6245 次

发布时间：2019-06-22

本文共 1392 字，大约阅读时间需要 4 分钟。

41. First Missing Positive

题目

Given an unsorted integer array, find the first missing positive integer.For example,Given [1,2,0] return 3,and [3,4,-1,1] return 2.Your algorithm should run in O(n) time and uses constant space.

解析

// add 41. First Missing Positiveclass Solution {public:    //对于每个数i调整到i-1位置，当然调整后还要接着判断。    //最后重头扫一遍，发现第一个a[i]!=i+1位置的就返回i+1；    int firstMissingPositive(vector
    
     & nums) { //数组约定为1-n吗？                for (int i = 0; i < nums.size();i++)        {            if (nums[i]>0&&nums[i]<=nums.size()&&nums[i]!=nums[nums[i]-1]) // [3,4,-1,1] //用if不能一直将元素放入正确的位置，eg：1需要交换两次才行            while (nums[i]>0 && nums[i] <= nums.size() && nums[i] != nums[nums[i] - 1])             {                swap(nums[i],nums[nums[i]-1]);            }        }        for (int i = 0; i < nums.size();i++)        {            if (nums[i]!=i+1)            {                return i+1;            }        }        return nums.size()+1; // 空或者本身有序，缺失最后一个    }    int firstMissingPositive(int A[], int n) {        for (int i = 0; i < n; i++)        {            while (A[i] > 0 && A[i] <= n && A[i] != A[A[i] - 1])            {                swap(A[i], A[A[i] - 1]);            }        }        for (int i = 0; i < n; i++)        {            if (A[i] != i + 1)            {                return i + 1;            }        }        return n + 1; // 空或者本身有序，缺失最后一个    }};