作者babelism (Bob)
看板C_and_CPP
标题[分享] Codility demo sample
时间Mon Sep 3 22:08:06 2018
说是心得嘛... 当灌水也行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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1535983690.A.ED1.html
1F：推 fatrabitree: 第一个if题目有提吗 09/03 22:20
2F：推 a21802: 如果只是要最小正整数 从1开始跑发现不在A里直接跳出不是 09/03 22:23
3F：→ a21802: 更好吗 09/03 22:23
4F：→ a21802: 还是我漏了什麽 09/03 22:24
5F：→ a21802: 我的想法会造成双层回圈 请无视 09/03 22:32
6F：推 alan23273850: 总觉得开阵列解的方法有点弱，有没有不用阵列的方 09/04 09:54
7F：→ alan23273850: 法？ 09/04 09:54
如果对 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;
}
不过我个人不太喜欢这解法。
8F：→ sarafciel: 空间复杂度O(1)的话就快排後扫一遍吧 会慢一点就是 09/04 10:41
9F：→ adrianshum: 严格来说这个的空间复杂度也是O(1) 吧，只是 constant 09/04 12:25
10F：→ adrianshum: term 很大而已 09/04 12:25
11F：→ adrianshum: 对不起，请无视，我看错code 每次都allocate bool[100 09/04 12:29
12F：→ adrianshum: 000] 了 09/04 12:29
※ 编辑: babelism (61.218.44.76), 09/04/2018 17:00:48
13F：推 oToToT: 不是该用size_t吗OAO 09/04 18:52
14F：推 oToToT: 顺便问一下原来现在可以直接宣告bool A[(non constant)]？ 09/04 18:55
15F：推 alan23273850: 原po後来回的那篇STL解法时间应该是O(nlgn)吧 09/05 06:50
16F：→ sarafciel: C99的话VLA已经是标准了 C++目前还是不行的样子 09/05 10:25
17F：推 alan23273850: cutekid 大大刚刚有水球我说排序过後不用那个 do-wh 09/05 15:25
18F：→ alan23273850: ile 回圈，可以 linear time 扫过去，请各位检查看 09/05 15:26
19F：→ alan23273850: 看是不是如此，不过还是 O(nlgn) 就是 09/05 15:26
20F：→ sarafciel: 是的 直接回圈扫一遍就好了 原PO这样写其实二分搜寻没 09/05 19:34
21F：→ sarafciel: 有发挥到 时间复杂度的瓶颈在sort上 所以依然是O(nlgn) 09/05 19:37