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.
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.
bucket sort
public class Solution { public int firstMissingPositive(int[] A) { //Time: O(n) Space: O(1) if (A == null || A.length == 0) { return 1; } for (int i = 0; i < A.length; i++) { while (A[i] > 0 && A[i] <= A.length && A[i] != i + 1) { int temp = A[i]; //if same, don't need swap if (A[temp - 1] == A[i]) { break; } A[i] = A[temp - 1]; A[temp - 1] = temp; } } for (int i = 0; i < A.length; i++) { if (A[i] != i + 1) { return i + 1; } } return A.length + 1; } }
No comments:
Post a Comment