41. First Missing Positive
https://leetcode.com/problems/first-missing-positive/
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0] Output: 3
Example 2:
Input: [3,4,-1,1] Output: 2
Example 3:
Input: [7,8,9,11,12] Output: 1
Note:
Your algorithm should run in O(n) time and uses constant extra space.
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int firstMissingPositive(int[] nums) { | |
| // first pass => put each number in its right position | |
| for (int i = 0; i < nums.length; i++) { | |
| while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) { | |
| int temp = nums[i]; | |
| // put element in intermediate position | |
| nums[i] = nums[nums[i] - 1]; | |
| // put element in right position | |
| nums[temp - 1] = temp; | |
| } | |
| } | |
| // second pass => return 1st number not in its right position | |
| for (int i = 0; i < nums.length; i++) { | |
| if (nums[i] != i + 1) { | |
| return i + 1; | |
| } | |
| } | |
| return nums.length + 1; | |
| } | |
| } |
