[分享] Codility demo sample

[babelism (Bob)]

說是心得嘛... 當灌水也行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題目有提嗎
推 a21802: 如果只是要最小正整數 從1開始跑發現不在A裡直接跳出不是
→ a21802: 更好嗎
→ a21802: 還是我漏了什麼
→ a21802: 我的想法會造成雙層迴圈 請無視
推 alan23273850: 總覺得開陣列解的方法有點弱，有沒有不用陣列的方
→ alan23273850: 法？
如果對 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)的話就快排後掃一遍吧 會慢一點就是
→ adrianshum: 嚴格來說這個的空間複雜度也是O(1) 吧，只是 constant
→ adrianshum:  term 很大而已
→ adrianshum: 對不起，請無視，我看錯code 每次都allocate bool[100
→ adrianshum: 000] 了
※ 編輯: babelism (61.218.44.76), 09/04/2018 17:00:48
推 oToToT: 不是該用size_t嗎OAO
推 oToToT: 順便問一下原來現在可以直接宣告bool A[(non constant)]？
推 alan23273850: 原po後來回的那篇STL解法時間應該是O(nlgn)吧
→ sarafciel: C99的話VLA已經是標準了  C++目前還是不行的樣子
推 alan23273850: cutekid 大大剛剛有水球我說排序過後不用那個 do-wh
→ alan23273850: ile 迴圈，可以 linear time 掃過去，請各位檢查看
→ alan23273850: 看是不是如此，不過還是 O(nlgn) 就是
→ sarafciel: 是的 直接迴圈掃一遍就好了 原PO這樣寫其實二分搜尋沒
→ sarafciel: 有發揮到 時間複雜度的瓶頸在sort上 所以依然是O(nlgn)
推 alvinpon: http://codepad.org/nIN4qy0c