為什麼這篇codility解答鄉民發文收入到精華區：因為在codility解答這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者babelism (Bob)看板C_and_CPP標題[分享] Codility demo sa...
說是心得嘛... 當灌水也行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
推 fatrabitree: 第一個if題目有提嗎 09/03 22:20
推 a21802: 如果只是要最小正整數 從1開始跑發現不在A裡直接跳出不是 09/03 22:23
→ a21802: 更好嗎 09/03 22:23
→ a21802: 還是我漏了什麼 09/03 22:24
→ a21802: 我的想法會造成雙層迴圈 請無視 09/03 22:32
推 alan23273850: 總覺得開陣列解的方法有點弱，有沒有不用陣列的方 09/04 09:54
→ 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;
}
不過我個人不太喜歡這解法。
→ sarafciel: 空間複雜度O(1)的話就快排後掃一遍吧 會慢一點就是 09/04 10:41
→ adrianshum: 嚴格來說這個的空間複雜度也是O(1) 吧，只是 constant 09/04 12:25
→ adrianshum: term 很大而已 09/04 12:25
→ adrianshum: 對不起，請無視，我看錯code 每次都allocate bool[100 09/04 12:29
→ adrianshum: 000] 了 09/04 12:29
※ 編輯: babelism (61.218.44.76), 09/04/2018 17:00:48推 oToToT: 不是該用size_t嗎OAO 09/04 18:52
推 oToToT: 順便問一下原來現在可以直接宣告bool A[(non constant)]？ 09/04 18:55
推 alan23273850: 原po後來回的那篇STL解法時間應該是O(nlgn)吧 09/05 06:50
→ sarafciel: C99的話VLA已經是標準了 C++目前還是不行的樣子 09/05 10:25
推 alan23273850: cutekid 大大剛剛有水球我說排序過後不用那個 do-wh 09/05 15:25
→ alan23273850: ile 迴圈，可以 linear time 掃過去，請各位檢查看 09/05 15:26
→ alan23273850: 看是不是如此，不過還是 O(nlgn) 就是 09/05 15:26
→ sarafciel: 是的 直接迴圈掃一遍就好了 原PO這樣寫其實二分搜尋沒 09/05 19:34
→ sarafciel: 有發揮到 時間複雜度的瓶頸在sort上 所以依然是O(nlgn) 09/05 19:37