find the first missing positive number# JobHunting - 待字闺中
g*j
1 楼
这个问题的基本思路就是交换，然后把合适的数放在合适的位置
比如 -1,3,1,4
交换之后便成 1,-1,3,4
代码如下
但是我有一个地方想不明白
A[i] != A[A[i] - 1]
这个是什么意思？
为什么不是 A[i] != i+1?
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
int firstMissingPositive(int A[], int n) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if(n == 0) return 1;
for(int i = 0; i < n; i++){
while (A[i] >=1 && A[i] <=n && A[i] != A[A[i] - 1]) {
swap(&A[i], &A[A[i]-1]);
}
}
for(int i = 0; i < n; i++) {
if(A[i] - 1 != i)
return i+1;
}
return n+1;
}
比如 -1,3,1,4
交换之后便成 1,-1,3,4
代码如下
但是我有一个地方想不明白
A[i] != A[A[i] - 1]
这个是什么意思？
为什么不是 A[i] != i+1?
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
int firstMissingPositive(int A[], int n) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if(n == 0) return 1;
for(int i = 0; i < n; i++){
while (A[i] >=1 && A[i] <=n && A[i] != A[A[i] - 1]) {
swap(&A[i], &A[A[i]-1]);
}
}
for(int i = 0; i < n; i++) {
if(A[i] - 1 != i)
return i+1;
}
return n+1;
}