Keshawn_lu's Blog

Leetcode 41. 缺失的第一个正数

数组
字数统计: 458阅读时长: 2 min
2020/06/27 Share

题目简介：

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

思路：

由于时间复杂度为O(n)，空间复杂度为O(1)，所以不能使用简单的哈希表或排序等方法。

所以我们使用置换的方法，在遍历数组时，将nums[i]放置到nums[nums[i] - 1]的位置上，比如nums[i] = 3就放置到nums[2]，即nums[2] = 3。

这样子最后的结果数组便为[1,2,3,4,...,nums.size()]。只要nums[i] != i + 1，那么这个数就是缺失的数，返回即可。

在置换时需要考虑以下几点：

  1. 首先0 < nums[i] <= nums.size()，也就是1 ~ nums.size()的范围，才可以进行置换。
  2. 若nums[i] == nums[nums[i] - 1]，即该位置上已放置了正确的数字，那么不必再置换，否则会造成死循环，一直置换下去。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {

        for(int i = 0; i < nums.size(); i++){

            while(nums[i] != i + 1){    //不为正确的数字

                //不在1 ~ nums.size()范围内
                if(nums[i] <= 0 || nums[i] > nums.size())
                    break;
                //num[nums[i] - 1]位置上已经放置了正确的数字，不必再交换，否则会是死循环
                if(nums[i] == nums[nums[i] - 1])
                    break;
                
                //交换，使nums[i]放置到正确位置
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;     //新的nums[i]
            }
        }

        for(int i = 0; i < nums.size(); i++){

            if(nums[i] != i + 1)
                return i + 1;
        }

        return nums.size() + 1;
        
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网