Problem: Given an unsorted integer array, find the smallest missing positive integer. Please note that 0 is not a missing positive integer.
Example:
Input: nums = [1,3,4] Output: 2
Approach: We can do it using external hash table / binary tree / heap or we can use sorting but it will be expensive in terms of space and time. We can use the input array itself for hashing. Please look at the two different approaches in the implementation.
Implementation in C#:
Approach 1: Using long.MaxValue for indicating that number exist
public int FirstMissingPositive(int[] nums)
{
int len = nums.Length;
long[] longCopyNums = new long[len];
for (int i = 0; i < len; ++i)
{
longCopyNums[i] = nums[i];
}
for (int i = 0; i < len; ++i)
{
if (longCopyNums[i] <= 0)
{
continue;
}
long j = longCopyNums[i];
while (j > 0 && j <= len)
{
long index = longCopyNums[j - 1];
longCopyNums[j - 1] = long.MaxValue;
j = index;
}
}
for (int i = 0; i < len; ++i)
{
if (longCopyNums[i] != long.MaxValue)
{
return i + 1;
}
}
return len + 1;
}
Approach 2: Using negative value to indicate the number exist
public int FirstMissingPositive(int[] nums)
{
int len = nums.Length;
bool containsOne = false;
foreach(int num in nums)
{
if (num == 1)
{
containsOne = true;
break;
}
}
if (!containsOne)
{
return 1;
}
if (len == 1)
{
return 2;
}
for (int i = 0; i < len; ++i)
{
if (nums[i] <= 0 || nums[i] > len)
{
nums[i] = 1;
}
}
for (int i = 0; i < len; ++i)
{
int index = Math.Abs(nums[i]) - 1;
if (nums[index] > 0)
{
nums[index] = -nums[index];
}
}
for (int i = 1; i < len; ++i)
{
if (nums[i] > 0)
{
return i + 1;
}
}
return len + 1;
}
Complexity: O(n)
No comments:
Post a Comment