Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/41.html
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.
Your algorithm should run in O(n) time and uses constant space.
@tag-array
Algorithm
Put 1
in the first position nums[0]
of the array and 2
in the second position nums[1]
, that is, you need to put nums[i]
on nums[nums[i]-1]
to traverse the entire array,
- If
nums[i] != i + 1
, andnums[i]
is an integer and is not greater than n, andnums[i]
is not equal tonums[nums[i]-1]
, swap the two positions, - if not satisfied above conditions are skipped directly, and the array is traversed again. If the number at the corresponding position is incorrect, the correct number will be returned.
Note
The key is to deal with the collision. If there are repeated
numbers 1, 1, or 2, 2. If the collision means that there is the correct number at the correct position, ++
will go to the next one.
Code
Java
-
import java.util.Arrays; public class First_Missing_Positive { public class Solution { public int firstMissingPositive(int[] nums) { if (nums == null || nums.length == 0) { return 1; } // two pointers, in plcace sort int i = 0; while (i < nums.length) { while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) { // put nums[i] to index nums[i]-1 int digit = nums[i]; int swapIndex = digit - 1; int tmp = nums[swapIndex]; nums[swapIndex] = digit; nums[i] = tmp; } i++; } // another scan for the missing one for (int j = 0; j < nums.length; j++) { if (nums[j] != j + 1) { return j + 1; } } // @note: case for [1,2,3,4,5] return nums.length + 1; } }
-
// OJ: https://leetcode.com/problems/first-missing-positive/ // Time: O(N) // Space: O(1) class Solution { public: int firstMissingPositive(vector<int>& A) { int i, N = A.size(); for (i = 0; i < N; ) { if (A[i] == i + 1 || A[i] < 1 || A[i] >= N + 1 || A[i] == A[A[i] - 1]) ++i; else swap(A[i], A[A[i] - 1]); } for (i = 0; i < N && A[i] == i + 1; ++i); return i + 1; } };
-
class Solution: def firstMissingPositive(self, nums: List[int]) -> int: def swap(i, j): nums[i], nums[j] = nums[j], nums[i] n = len(nums) for i in range(n): while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]: swap(i, nums[i] - 1) for i in range(n): if i + 1 != nums[i]: return i + 1 return n + 1 ############ class Solution(object): def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ i = 0 while i < len(nums): if 0 < nums[i] <= len(nums) and nums[nums[i] - 1] != nums[i]: nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] else: i += 1 for i in range(0, len(nums)): if nums[i] != i + 1: return i + 1 return len(nums) + 1