Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
Example 1:
Input: nums = [1,2,0] Output: 3
Example 2:
Input: nums = [3,4,-1,1] Output: 2
Example 3:
Input: nums = [7,8,9,11,12] Output: 1
Constraints:
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1
Solution: Marking
First pass, marking nums[i] to INT_MAX if nums[i] <= 0
Second pass, use a negative number to mark the presence of a number x at nums[x – 1]
Third pass, the first positive number is the missing index i, return i +1
If not found return n + 1.
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int firstMissingPositive(vector<int>& nums) { const int n = nums.size(); for (int& x : nums) if (x <= 0) x = INT_MAX; for (int x : nums) { x = abs(x); if (x >= 1 && x <= n && nums[x - 1] > 0) nums[x - 1] *= -1; } for (int i = 0; i < n; ++i) if (nums[i] > 0) return i + 1; return n + 1; } }; |