LeetCode 0041 - First Missing Positive
# Hints
- 思维
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
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 time and uses constant extra space.
# 题意
给定一个长为 的数组 ,求最小的不在数组中的正整数是多少。
# 题解
问题本身很简单,难在 的时间限制和 的额外空间限制,否则排序或哈希即可解决问题。
方法不止一种,但都比较trick,很难想到。
其中一种方法是,对于每个正整数 ,若 ,我们就通过交换将其放置到 处。由于每次交换一定能使得某个数放置到对应的位置上,所以至多 次交换即可完成。
这样一来,我们只需顺序遍历整个数组,当发现 或 时,即可确定 为答案。
# AC代码
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]);
}
}
// 返回
for (int x = 1; x <= n; x ++) {
if (x != nums[x - 1]) {
return x;
}
}
return (n + 1);
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01