First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
Example
Given [1,2,0]
return 3
, and [3,4,-1,1]
return 2
.
Challenge
Your algorithm should run in O(n) time and uses constant space.
public int firstMissingPositive(int[] A) { if (A.length == 0) { return 1; } int i = 0; while (i < A.length) { if (A[i] != i + 1) { if (A[i] <= A.length && A[i] > 0 && A[A[i] - 1] != A[i]) { swap(A, i, A[i] - 1); } else { A[i] = 0; i++; } } else { i++; } } for (int j = 0; j < A.length; j++) { if (j + 1 != A[j]) { return j + 1; } } return A.length + 1; } public void swap(int[] nums, int a, int b) { int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp; }