codility上的练习（2）

codility新增了练习lesson 2。

有三个题:

(1) Perm-Check

给定整数数组有N个数，问它是不是1-N的一个排列，也就是说是否每个数都是1-N,并且只出现一次。输出1和0表示是与否，输入范围N [1..10^5],数组里地整数[1..10^5]，要求复杂度时间空间都是O(N)。

分析：空间复杂度O(N)的算法很简单，我们可以建立一个bool数组表示1-N，每个数是否出现过。代码如下：

// you can also use includes, for example:// #include <algorithm>vector<int> solution(int N, vector<int> &A) {    // write your code here...    int i,m = A.size(), lastv = 0, v = 0;    vector<int> r;    r.resize(N , 0);    for (i = 0; i < m; ++i) {        if (--A[i] < N) {            v = max(v, r[A[i]] = max(r[A[i]], lastv) + 1);        }        else {            lastv = v;        }    }    for (i = 0; i < N; ++i) {        r[i] = max(r[i], lastv);    }    return r;            }

1楼spacejohn2小时前

您好，非常喜欢您分享的codility的经验，有个问题想请教您，这个题库每个月会变，还是什么情况的，我看您2012年的有近10个，2013年目前只有4个。谢谢