[LeetCode] 41. First Missing Positive 首个缺失的正数
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Note:
Your algorithm should run in O(n) time and uses constant extra space.
这道题让我们找缺失的首个正数，由于限定了 O(n) 的时间，所以一般的排序方法都不能用，最开始博主没有看到还限制了空间复杂度，所以想到了用 HashSet 来解，这个思路很简单，把所有的数都存入 HashSet 中，然后循环从1开始递增找数字，哪个数字找不到就返回哪个数字，如果一直找到了最大的数字（这里是 nums 数组的长度），则加1后返回结果 res，参见代码如下：
解法一：
// NOT constant space
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
unordered_set<int> st(nums.begin(), nums.end());
int res = , n = nums.size();
while (res <= n) {
if (!st.count(res)) return res;
++res;
}
return res;
}
};
但是上面的解法不是 O(1) 的空间复杂度，所以需要另想一种解法，既然不能建立新的数组，那么只能覆盖原有数组，思路是把1放在数组第一个位置 nums[0]，2放在第二个位置 nums[1]，即需要把 nums[i] 放在 nums[nums[i] - 1]上，遍历整个数组，如果 nums[i] != i + 1, 而 nums[i] 为整数且不大于n，另外 nums[i] 不等于 nums[nums[i] - 1] 的话，将两者位置调换，如果不满足上述条件直接跳过，最后再遍历一遍数组，如果对应位置上的数不正确则返回正确的数，参见代码如下：
解法二：
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = ; i < n; ++i) {
while (nums[i] > && nums[i] <= n && nums[nums[i] - ] != nums[i]) {
swap(nums[i], nums[nums[i] - ]);
}
}
for (int i = ; i < n; ++i) {
if (nums[i] != i + ) return i + ;
}
return n + ;
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/41
类似题目：
Find All Numbers Disappeared in an Array
参考资料：
https://leetcode.com/problems/first-missing-positive/
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- npm淘宝镜像cnpm
- 【Python】列表各种操作
- Android 更改字体
- Newtonsoft.Json（C#处理json）
- memcache c++使用
- python如何控制数据库？
- SVN命令使用详解
- Js作用域与作用域链详解
- CSS如何实现图片上下垂直居中
- 浅析c语言中的变量(局部变量，外部变量，静态变量，寄存器变量）[转]
- Ubuntu Telnet 配置(openbsd-inetd)
- [Android]在Dagger 2中Activities和Subcomponents的多绑定（翻译）
- 网页版 treeview使用中遇到的问题
- 使用Flex图表组件
- WinEdt7.0 初试
- objective-c 中数据类型之中的一个 几何数据类型（CGPoint,CGSize,CGRect）
- Linux之 网卡发包、接包 error 、droped 情况
- ArcEngine GroupLayer监听图层改变
- React 入门实例教程（转载）
- Css3新属性：calc()