g***j 发帖数: 1275 | 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;
} | J****3 发帖数: 427 | 2 Bucket sort 变体哇 对应正确的桶位置 |
|