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
Follow up:
Your algorithm should run in O(n) time and uses constant extra space.
C++
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
if(nums.size()==0)return 1;
if(nums.size()==1)
if(nums[0]>1||nums[0]<1)
return 1;
else if(nums[0]==1)
return 2;
unordered_map<int,int> mp;
for(int i=0;i<nums.size();++i)
{
if(nums[i]>0)
{
mp[nums[i]]++;
}
}
long long int n=*max_element(nums.begin(),nums.end());
if(n<1)return 1;
int i=1;
while(i<=n)
{
if(mp[i]==0)
return i;
++i;
}
return n+1;
}
};
--------------------------------------------------------------------------------------------------------------------------------------
Put each number in the right place.
For example:
When we find 5, then swap it with A[4].
At last, the first place where its number is not right,
return the place + 1.
class Solution
{
public:
int firstMissingPositive(int A[], int n)
{
for(int i = 0; i < n; ++ i)
while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
swap(A[i], A[A[i] - 1]);
for(int i = 0; i < n; ++ i)
if(A[i] != i + 1)
return i + 1;
return n + 1;
}
};
---------------------------------------------------------------------------------------------------------------------------------------
PYTHON
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
Basic idea:
1. for any array whose length is l, the first missing
positive must be in range [1,...,l+1],
so we only have to care about those elements in this
range and remove the rest.
2. we can use the array index as the hash to restore the
frequency of each number within
the range [1,...,l+1]
"""
nums.append(0)
n = len(nums)
for i in range(len(nums)): #delete those useless elements
if nums[i]<0 or nums[i]>=n:
nums[i]=0
for i in range(len(nums)): #use the index as the hash to
record the frequency of each number
nums[nums[i]%n]+=n
for i in range(1,len(nums)):
if nums[i]/n==0:
return i
return n
---------------------------------------------------------------------------------------------------------------------------------------------
JAVA
This code takes advantage of two insights:Numbers greater then n can be ignored because the missing integer must be in the range 1..n+1
If each cell in the array were to contain positive integers only,
we can use the negative of the stored number as a flag to mark something (in this case the flag indicates this index was found in some cell of the array)
public class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 1. mark numbers (num < 0) and (num > n) with a special
marker number (n+1)
// (we can ignore those because if all number are > n then
we'll simply return 1)
for (int i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = n + 1;
}
}
// note: all number in the array are now positive, and on
the range 1..n+1
// 2. mark each cell appearing in the array, by converting
the index for that number to negative
for (int i = 0; i < n; i++) {
int num = Math.abs(nums[i]);
if (num > n) {
continue;
}
num--; // -1 for zero index based array
(so the number 1 will be at pos 0)
if (nums[num] > 0) {
// prevents double negative operations
nums[num] = -1 * nums[num];
}
}
// 3. find the first cell which isn't negative
(doesn't appear in the array)
for (int i = 0; i < n; i++) {
if (nums[i] >= 0) {
return i + 1;
}
}
// 4. no positive numbers were found, which means
the array contains all numbers 1..n
return n + 1;
}
}
