一. 題目描述
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.
二. 題目分析
該題的大意是給定一個未排序的數組,該數組可能包含零或正負數,要求找出第一個未出現的正數。例如[1, 2, 0]
,由於第一個未出現的正整數是3
,則返回3
;[3, 4, -1, 1]
第一個未出現的正整數是2
,則返回2
。算法要求在O(n)
的時間復雜度及常數空間復雜度內完成。
一種方法是,先把數組裡每個正整數從i
位放到第i-1
位上,這樣就形成了有序的序列,然後檢查每一下標index
與當前元素值,就能知道當前下標所對應的正整數是否缺失,若缺失則返回下標index + 1
即可。
三. 示例代碼
#include
#include
using namespace std;
class Solution
{
public:
int firstMissingPositive(vector& nums)
{
int n = nums.size();
for (int i = 0; i < n; ++i)
{
int temp = 0;
while (i + 1 != nums[i] && nums[i] != nums[nums[i] - 1] && nums[i] > 0)
{
temp = nums[i];
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
}
}
for (int i = 0; i < n; ++i)
{
if (i + 1 != nums[i])
return i + 1;
}
return n + 1;
}
};