• First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
Solution:
1. public class Solution {
2. public int firstMissingPositive(int[] a) {
3. int i = 0;
4. while (i < a.length) {
5. if (a[i] > 0 && a[i] <= a.length && a[i] != a[a[i] - 1]) {
6. swap(a, i, a[i] - 1);
7. } else {
8. i++;
9. }
10. }
11. 12. i = 0;
13. while (i < a.length && a[i] == i + 1) {
14. i++;
15. }
16. 17. return i + 1;
18. }
19. 20. void swap(int[] a, int i, int j) {
21. int b = a[i];
22. a[i] = a[j];
23. a[j] = b;
24. }
25. }