Leetcode-41.缺失的第一个正数

发表于 分类于 阅读次数：

题目描述

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

示例 1:

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

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

输入: [7,8,9,11,12]
输出: 1
说明:

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

解法1：桶排序

思路：

1.”一个萝卜1个坑“，即以自身作为hash表，将自身放入对应位置，例如nums[3]=2，那么就让他放入自身的第2个位置，即swap(nums[nums[3]-1],nums[3]),然后对交换过来的元素进行操作

2.如果该数的范围<=0||>n则自身没有地方放该数，那么就让该数在原地，不对他进行操作

3.如果要换的位置已经放入了正确的数，则跳出循环，对下一个nums[i]进行操作

4.遍历自身数组，当nums[i]!=i-1时，即该位置缺少对应的数，则找到了最小的缺失正数，返回，若遍历发现没有缺失，表示该数组从1到n,都有数字，则返回n+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        int i;
        for(i=0;i<n;i++)
        {
            while(nums[i]>0&&nums[i]<=n)
            {
                if(nums[i]==nums[nums[i]-1])
                    break;
                swap(nums[i],nums[nums[i]-1]);
            }
        }
        for(i=0;i<n;i++)
        {
            if(nums[i]!=i+1)
                return i+1;
        }
        return n+1;
    }
};