Leetcode第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

方法一(使用hash表解决):

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //使用hash解决
        unordered_map<int,int> order;

        //将hash表中对应位置元素置1
        for(int i = 0;i < nums.size();i++)
            order[nums[i]]++;

        //遍历hash表,找到第一个值不为1的下标i直接返回即可
        //从1开始遍历是为了去除nums数组中有值为0的情况
        for(int i = 1;i <= nums.size();i++){
            if(!order[i])
            return i;
        }
        //遍历结束没有找到值为0的元素直接返回数组大小加一
        return nums.size() + 1;
    }
};

方式二(调整数组元素位置):

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        //将数组元素调整到正确的位置
        for(int i = 0;i < n;i++){
            while(nums[i] >= 1 && nums[i] < n && nums[i] != nums[nums[i] - 1])
                swap(nums[i],nums[nums[i] - 1]);
        }

        //遍历数组,找到数组 下标+1 与存储的元素不对应的直接返回
        for(int i = 0;i < n;i++)
            if(nums[i] != i + 1) return i + 1;

        //遍历完成,均符合,最小正数为数组长度加一
        return n + 1;
    }
};