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; }