[分享] Codility demo sample
說是心得嘛... 當灌水也行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;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.147.15.203
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1535983690.A.ED1.html
推
09/03 22:20,
7年前
, 1F
09/03 22:20, 1F
推
09/03 22:23,
7年前
, 2F
09/03 22:23, 2F
→
09/03 22:23,
7年前
, 3F
09/03 22:23, 3F
→
09/03 22:24,
7年前
, 4F
09/03 22:24, 4F
→
09/03 22:32,
7年前
, 5F
09/03 22:32, 5F
推
09/04 09:54,
7年前
, 6F
09/04 09:54, 6F
→
09/04 09:54,
7年前
, 7F
09/04 09:54, 7F
如果對 STL 熟悉的話，可以這樣寫，不用開 array，也是滿分解法
int solution(vector<int> &A) {
int result = 1;
bool found = false;
sort(A.begin(), A.end());
do
{
found = binary_search(A.begin(), A.end(), result);
if (found)
{
result++;
}
} while (found);
return result;
}
不過我個人不太喜歡這解法。
→
09/04 10:41,
7年前
, 8F
09/04 10:41, 8F
→
09/04 12:25,
7年前
, 9F
09/04 12:25, 9F
→
09/04 12:25,
7年前
, 10F
09/04 12:25, 10F
→
09/04 12:29,
7年前
, 11F
09/04 12:29, 11F
→
09/04 12:29,
7年前
, 12F
09/04 12:29, 12F
※ 編輯: babelism (61.218.44.76), 09/04/2018 17:00:48
推
09/04 18:52,
7年前
, 13F
09/04 18:52, 13F
推
09/04 18:55,
7年前
, 14F
09/04 18:55, 14F
推
09/05 06:50,
7年前
, 15F
09/05 06:50, 15F
→
09/05 10:25,
7年前
, 16F
09/05 10:25, 16F
推
09/05 15:25,
7年前
, 17F
09/05 15:25, 17F
→
09/05 15:26,
7年前
, 18F
09/05 15:26, 18F
→
09/05 15:26,
7年前
, 19F
09/05 15:26, 19F
→
09/05 19:34,
7年前
, 20F
09/05 19:34, 20F
→
09/05 19:37,
7年前
, 21F
09/05 19:37, 21F
推
09/09 10:37,
7年前
, 22F
09/09 10:37, 22F