题解 | 数组Mex
数组Mex
https://www.nowcoder.com/practice/9e7a6bcdbce74feb8013d252d76855da
解题思路
这是一个查找未出现最小正整数的问题。由于数组大小不超过500，所以最小未出现的正整数一定不会超过501。
关键点：
- 最小未出现正整数的范围是
- 可以使用原数组作为标记数组
- 将每个在范围内的正整数放到对应位置
算法步骤：
- 遍历数组，将每个在
范围内的数放到对应位置
- 再次遍历数组，找到第一个位置
上的数不是
的位置
- 该位置
代码
class ArrayMex {
public:
int findArrayMex(vector<int>& A, int n) {
// 将每个数放到正确的位置
for (int i = 0; i < n; i++) {
while (A[i] > 0 && A[i] <= n && A[A[i]-1] != A[i]) {
swap(A[i], A[A[i]-1]);
}
}
// 找到第一个不在正确位置的数
for (int i = 0; i < n; i++) {
if (A[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
};
import java.util.*;
public class ArrayMex {
public int findArrayMex(int[] A, int n) {
// 将每个数放到正确的位置
for (int i = 0; i < n; i++) {
while (A[i] > 0 && A[i] <= n && A[A[i]-1] != A[i]) {
int temp = A[i];
A[i] = A[temp-1];
A[temp-1] = temp;
}
}
// 找到第一个不在正确位置的数
for (int i = 0; i < n; i++) {
if (A[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
class ArrayMex:
def findArrayMex(self, A, n):
i = 0
while i < n:
if A[i] > 0 and A[i] <= n and A[A[i]-1] != A[i]:
A[A[i]-1], A[i] = A[i], A[A[i]-1]
else:
i += 1
for i in range(n):
if A[i] != i + 1:
return i + 1
return n + 1
算法及复杂度
- 算法：原地哈希
- 时间复杂度：
，每个数最多被交换一次
- 空间复杂度：
，只使用常数额外空间
