Given an unsorted list of integers nums, return the smallest positive integer (1, 2, 3, ...) that is not in the list. Numbers that are zero or negative do not count.
Your solution must run in O(n) time and use only O(1) extra space.
Examples
Example 1:
Input: nums = [3,1,4]
Output: 2
Explanation: 1 is there, 2 is not. The answer is 2.
Example 2:
Input: nums = [1,2,3,4]
Output: 5
Explanation: 1 to 4 are all there, so the next positive integer, 5, is missing.
Example 3:
Input: nums = [-5,0,2,2]
Output: 1
Explanation: Even 1 is missing. Negative numbers and 0 do not help.