Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
1 2
|
Input: [1,2,0] Output: 3
|
Example 2:
1 2
|
Input: [3,4,-1,1] Output: 2
|
Example 3:
1 2
|
Input: [7,8,9,11,12] Output: 1
|
Note:
Your algorithm should run in O(n) time and uses constant extra space.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
class { public int firstMissingPositive(int[] nums) { if (nums == null || nums.length == 0) return 1; for (int i = 0; i < nums.length;) { int n = nums[i]; if (n > 0 && n < nums.length) { if (nums[n - 1] != n) { nums[i] = nums[n - 1]; nums[n - 1] = n; i--; } } i++; } for (int i = 0; i < nums.length; i++) { if (nums[i] != i + 1) { return i + 1; } } return nums.length + 1; } }
|
近期评论