原地hash
可以用来找缺失的第一个数，或者是重复的数字。
给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数
进阶： 空间复杂度 $O(1)$ ，时间复杂度 $O(n)$ 。
数据范围：
$-2^{31} \le nums[i] \le 2^{31} - 1$
$0\le len(nums) \le 5 \times 10^5$
题解：
做法一：
原地hash操作，可以对存在的数字 $x$ ，在对应的下标 $nums[x]$ 上打上标记，这个标记可以是将其乘以 $-1$ 。
首先对 $ \le 0$ 的数变为 $n + 1$ 。
然后每次遇到 $nums[i]$ ，如果 $|nums[i]| \in [1, n]$ 则将 $nums[|nums[i - 1]| - 1]$ 变为 $-|nums[|nums[i - 1]| - 1]|$ 。注意需要取绝对值之后再取反。
再次遍历数组，如果遇到一个元素 $nums[i] \gt 0$ 则直接返回 $i + 1$ 。
做法二：
还可以使用交换的操作。把 $nums[i]$ 通过交换放到 $nums[nums[i] - 1]$ 的位置上，这样的话每个元素都有自己的位置。
首先，如果 $nums[i] \le 0$ ，将 $nums[i] = n + 1$ 。
然后每次遇到 $nums[i] \in [1, n]$ ，判断一下 $nums[nums[i] - 1] = nums[i]$ ，不相等的话就交换，直到二者相等。
最后再次遍历数组，如果遇到 $nums[i] \neq i + 1$ ，则直接返回 $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
| class Solution {
public:
int minNumberDisappeared(vector<int>& nums) {
int n = nums.size();
int x = 0;
for(int i = 0; i < n; ++i) {
if(nums[i] < 0) {
nums[i] = n + 1;
}
}
for(int i = 0; i < n; ++i) {
if(abs(nums[i]) >= 1 && abs(nums[i]) <= n) {
nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
}
}
for(int i = 0; i < n; ++i) {
if(nums[i] > 0) {
return i + 1;
}
}
return n + 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
33
34
35
| class Solution {
public:
int minNumberDisappeared(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] <= 0) {
nums[i] = n + 1;
}
}
for (int i = 0; i < n; ++i) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[nums[i] - 1], nums[i]);
}
}
int ans = n + 1;
for (int i = 0; i < n; ++i) {
if(nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
};
|
给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
题解：
也是使用原地hash操作。
做法一：
每次将 $nums[|nums[i]| - 1]$ 变成相反数，如果之前是负数，那么就需要把他加入答案，因为出现了两次。如果之前是正数，那么就变为负数，因为第一次出现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution
{
public:
vector<int> findDuplicates(vector<int> &nums)
{
int n = nums.size();
vector<int> ans;
for (int i = 0; i < n; ++i)
{
if(nums[abs(nums[i]) - 1] < 0) {
ans.emplace_back(abs(nums[i]));
} else {
nums[abs(nums[i]) - 1] = -1 * nums[abs(nums[i]) - 1];
}
}
return ans;
}
};
|
做法二：
使用交换操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution
{
public:
vector<int> findDuplicates(vector<int> &nums)
{
int n = nums.size();
vector<int> ans;
for (int i = 0; i < n; ++i)
{
while(nums[nums[i] - 1] != nums[i]) {
swap(nums[nums[i] - 1], nums[i]);
}
}
for(int i = 0; i < n; ++i) {
if(nums[i] != i + 1) {
ans.emplace_back(nums[i]);
}
}
return ans;
}
};
|