a***e
发帖数: 413 | 1 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.
我自己想的答案通过了OJ，但用的那个vector p(max+1,0);是不是会被说不是
constant space？其实我第一个想法就是最多是一个 INT_MAX大小的数组，不也是
constant space么？
class Solution {
public:
int firstMissingPositive(int A[], int n) {
int min = INT_MAX, max = INT_MIN;
for (int i=0; i
{
if (A[i]
if (A[i]>max) max=A[i];
}
if (min==0&&max==0) return 1;
if (min>1) return 1;
if (max<-1) return -1;
vector p(max+1,0);
for (int i=0; i
{
if (A[i]>0)
p[A[i]]++;
}
for (int i=1; i
{
if (p[i]==0)
return i;
}
return max+1;
}
};
但似乎别人的答案是下面zhege
class Solution {
public:
int firstMissingPositive(int A[], int n) {
for (int i = 0; i < n; ++i)
{
int num = A[i];
while (num <= n && num > 0 && A[num - 1] != num)
{
swap(A[num - 1], A[i]);
num = A[i];
}
}
for (int i = 0; i < n; ++i)
{
if (A[i] != i + 1)
{
return i + 1;
}
}
return n + 1;
}
}; | F*****o
发帖数: 32 | 2 你的solution应该不是constant space.因为你额外数组的大小是基于最大数的大小。
In this case: A=[1,2,3,4,...,n],it is O(n).
所谓的constant space,是指无论input是什么样子的数组，你的space是constant。
所以，本题要在原数组中做文章。 | a***e
发帖数: 413 | |
|
