public class Solution {
public int firstMissingPositive(int[] A) {
int n = A.length;
for (int i=0; i<n; i++) {
while (A[i] != i+1 && A[i]-1 >= 0 && A[i]-1 < n && A[i] != A[A[i]-1]) {
swap(A, i, A[i]-1);
}
}
for (int i=0; i<n; i++) {
if (A[i] != i+1) return i+1;
}
return n + 1;
}
void swap(int[] A, int i, int j) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
// 3,4,-1,1
// -1,4,3,1
// -1,1,3,4
//
cHVibGljIGNsYXNzIFNvbHV0aW9uIHsKICAgIHB1YmxpYyBpbnQgZmlyc3RNaXNzaW5nUG9zaXRpdmUoaW50W10gQSkgewogICAgICAgIGludCBuID0gQS5sZW5ndGg7CiAgICAgICAgZm9yIChpbnQgaT0wOyBpPG47IGkrKykgewogICAgICAgICAgICB3aGlsZSAoQVtpXSAhPSBpKzEgJiYgQVtpXS0xID49IDAgJiYgQVtpXS0xIDwgbiAmJiBBW2ldICE9IEFbQVtpXS0xXSkgewogICAgICAgICAgICAgICAgc3dhcChBLCBpLCBBW2ldLTEpOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKSB7CiAgICAgICAgICAgIGlmIChBW2ldICE9IGkrMSkgICAgcmV0dXJuIGkrMTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIG4gKyAxOwogICAgfQoKICAgIHZvaWQgc3dhcChpbnRbXSBBLCBpbnQgaSwgaW50IGopIHsKICAgICAgICBpbnQgdG1wID0gQVtpXTsKICAgICAgICBBW2ldID0gQVtqXTsKICAgICAgICBBW2pdID0gdG1wOwogICAgfQp9CgovLyAzLDQsLTEsMQovLyAtMSw0LDMsMQovLyAtMSwxLDMsNAovLwo=