1. 辅助数组
bool类型的1~n的数组记录数据的出现情况，n为数据的个数。
时间O(n)，空间O(n)。
2. 原地重排
题目要求空间是O(1)的，单纯使用额外变量又没法记录得到最小值，同时又不能使用额外的空间，因此考虑原地重排。
数据和位置的对应关系如下：
遍历每个数据，如果不满足i + 1 == nums[i]，则将当前的nums[i]数据与nums[nums[i] - 1]数据交换。
并将交换到i位置的数据也交换到其应该在的位置，直到当前位置满足上述条件或者交换过来的数据越界（负数或过大的正数）。
因为所有数据至多交换n次，所以时间复杂度O(n)，空间复杂度O(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
| class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
while (i + 1 != nums[i] && nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (i + 1 != nums[i]) {
ans = i + 1;
break;
}
}
if (ans == 0)
ans = n + 1;
return ans;
}
};
|