说是心得嘛... 当灌水也行XD
这是 Codility 的 demo sample，
提供一个满分解答。
(Codility 是程设训练平台，某些公司会用这个平台来面试)
====================
This is a demo task.
Write a function:
int solution(vector<int> &A);
that, given an array A of N integers, returns the smallest positive integer
(greater than 0) that does not occur in A.
For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [-1, -3], the function should return 1.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range
[-1,000,000..1,000,000]
给分的重点在于运算速度要快、对于上下限的处理要明确、
Compile 连 warning 都不能。时间复杂度在 O(N^2) 以上的都不及格。
限时30分钟。
==================== 范例码在下面 ====================
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
if (A.size() > 100000)
{
return 100001;
}
if (A.empty())
{
return 1;
}
bool ba[A.size()] = {false};
for (unsigned int ix = 0; ix < A.size(); ix++)
{
if (A[ix] < 1)
{
continue;
} else
{
if ((unsigned int)A[ix] > A.size())
{
continue;
}
}
ba[A[ix]-1] = true;
}
for (unsigned int ix = 0; ix < A.size(); ix++)
{
if (ba[ix] == false)
{
return ix+1;
}
}
return A.size() + 1;
}