Codility and other programming lessons: Lesson 8: Peaks (Peaks)
If no peeks are found, we return 0. If there is any peek, we start checking from the possible maximum number of blocks=the number of the peeks (each block must contains at least one peek).
int solution(int A[], int N)
{
//we need at least 3 elements to have a peek.
if (N < 3){
return 0;
}
//we will never have the number of peeks larger than N / 2.
int *peeks = (int*)alloca(sizeof(int) * (N / 2));
int peek_cnt = 0;
//find peeks
int i;
for (i = 1; i < N - 1; i++){
if (A[i - 1] < A[i] && A[i] > A[i + 1]){
peeks[peek_cnt++] = i;
}
}
//if there is no peek, return 0
if (peek_cnt == 0){
return 0;
}
//let's check from the block of the possible maxim number of blocks.
//as we have at least one peek, we can say the minimum number of blocks
//that meets the given condition is 1.
int maxdiv = 1;
for (i = peek_cnt; i > 0; i--){
if (N % i != 0){
continue;
}
//let's check if this number satisfies the conditon.
int elems_for_each_block = N / i;
int next_block_end = elems_for_each_block;
int pidx = 0; //the index of the peek to check
int flg = 1; //assume the number satisfies the condition first.
while(1){
//check if this block contains any peek.
if (pidx >= peek_cnt || next_block_end <= peeks[pidx]){
//no peeks detected, this is not a right choice.
flg = 0;
break;
}
//skip the peeks within the current block.
while(pidx < peek_cnt && peeks[pidx] < next_block_end){
pidx++;
}
next_block_end += elems_for_each_block;
if (next_block_end > N){
break;
}
}
//at least one peek is contained in every block.
if (flg){
maxdiv = i;
break;
}
}
return maxdiv;
}
I googled and found some people implemented a more efficient algorithm using the prefix sum. Instead of keeping the index of the peeks, they prepare another array that contains the prefix sum of the number of peeks found so far in the array A at the same index.
This strategy facilitate to check if the block size that is currently being examined satisfies the given condition or not.
https://github.com/yiqin/Codility-Practice/blob/master/Peaks.java
Read full article from Codility and other programming lessons: Lesson 8: Peaks (Peaks)
A non-empty zero-indexed array A consisting of N integers is given.
A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 < P < N − 1, A[P − 1] < A[P] and A[P] > A[P + 1].
For example, the following array A:
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2
has exactly three peaks: 3, 5, 10.
We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:
- A[0], A[1], ..., A[K − 1],
- A[K], A[K + 1], ..., A[2K − 1],
...- A[N − K], A[N − K + 1], ..., A[N − 1].
What's more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).
The goal is to find the maximum number of blocks into which the array A can be divided.
Array A can be divided into blocks as follows:
- one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
- two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
- three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.
However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].
The maximum number of blocks that array A can be divided into is three.
Write a function:
int solution(int A[], int N);
that, given a non-empty zero-indexed array A consisting of N integers, returns the maximum number of blocks into which A can be divided.
If A cannot be divided into some number of blocks, the function should return 0.
For example, given:
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2
the function should return 3, as explained above.
First, we find the peeks in the array A and store their index to another array.If no peeks are found, we return 0. If there is any peek, we start checking from the possible maximum number of blocks=the number of the peeks (each block must contains at least one peek).
int solution(int A[], int N)
{
//we need at least 3 elements to have a peek.
if (N < 3){
return 0;
}
//we will never have the number of peeks larger than N / 2.
int *peeks = (int*)alloca(sizeof(int) * (N / 2));
int peek_cnt = 0;
//find peeks
int i;
for (i = 1; i < N - 1; i++){
if (A[i - 1] < A[i] && A[i] > A[i + 1]){
peeks[peek_cnt++] = i;
}
}
//if there is no peek, return 0
if (peek_cnt == 0){
return 0;
}
//let's check from the block of the possible maxim number of blocks.
//as we have at least one peek, we can say the minimum number of blocks
//that meets the given condition is 1.
int maxdiv = 1;
for (i = peek_cnt; i > 0; i--){
if (N % i != 0){
continue;
}
//let's check if this number satisfies the conditon.
int elems_for_each_block = N / i;
int next_block_end = elems_for_each_block;
int pidx = 0; //the index of the peek to check
int flg = 1; //assume the number satisfies the condition first.
while(1){
//check if this block contains any peek.
if (pidx >= peek_cnt || next_block_end <= peeks[pidx]){
//no peeks detected, this is not a right choice.
flg = 0;
break;
}
//skip the peeks within the current block.
while(pidx < peek_cnt && peeks[pidx] < next_block_end){
pidx++;
}
next_block_end += elems_for_each_block;
if (next_block_end > N){
break;
}
}
//at least one peek is contained in every block.
if (flg){
maxdiv = i;
break;
}
}
return maxdiv;
}
Python solution: http://www.martinkysel.com/codility-peaks-solution/
irst, we need to find all the peaks. Simply iterate through all elements and aggregate all the peaks into P .
Then, we can iterate through the various possible group sizes g∈[1,N] . We need the least g such that g|N (then Ng is maximized) and so that every group of size g has at least one peak. This can be done by simply iterating through all the peaks p∈P and checking if every has peak.
public int solution(int[] A) {
int N = A.length;
// Find all the peaks
ArrayList<Integer> peaks = new ArrayList<Integer>();
for(int i = 1; i < N-1; i++){
if(A[i] > A[i-1] && A[i] > A[i+1]) peaks.add(i);
}
for(int size = 1; size <= N; size++){
if(N % size != 0) continue; // skip if non-divisible
int find = 0;
int groups = N/size;
boolean ok = true;
// Find whether every group has a peak
for(int peakIdx : peaks){
if(peakIdx/size > find){
ok = false;
break;
}
if(peakIdx/size == find) find++;
}
if(find != groups) ok = false;
if(ok) return groups;
}
return 0;
}This strategy facilitate to check if the block size that is currently being examined satisfies the given condition or not.
int solution(int A[], int N)
{
//for N < 3, there is no peek.
if (N < 3){
return 0;
}
//make the prefix sum of the number of the peeks at the index.
int* peek_cnt_prefix_sum = (int*)alloca(sizeof(int) * N);
peek_cnt_prefix_sum[0] = 0;
int i;
for (i = 1; i < N - 1; i++){
peek_cnt_prefix_sum[i] = peek_cnt_prefix_sum[i - 1];
if (A[i - 1] < A[i] && A[i] > A[i + 1]){
peek_cnt_prefix_sum[i]++;
}
}
peek_cnt_prefix_sum[N - 1] = peek_cnt_prefix_sum[N - 2];
//no peek found.
if (peek_cnt_prefix_sum[N - 1] == 0){
return 0;
}
int maxdiv = 1;
for (i = peek_cnt; i > 0; i--){
if (N % i != 0){
continue;
}
int elems_for_each_block = N / i;
//keep on checking
int flg = 1; //assume this divisor of N satisfies the condition.
int next_block_end = elems_for_each_block - 1;
int current = peek_cnt_prefix_sum[0];
while(next_block_end < N){
int next = peek_cnt_prefix_sum[next_block_end];
//no peeks found between current and next.
if (current >= next){
flg = 0;
break;
}
current = next;
next_block_end += elems_for_each_block;
}
//if this divisor of N satisfied the condition,
//it is the answer.
if (flg){
maxdiv = i;
break;
}
}
return maxdiv;
}
分析： 个人感觉时间复杂度很诡异……，首先如果我们用O(n)得空间统计从开始到目前为止得山峰数sum[]，那么我们如何检查某个k是不是一个可行解？
(a) 首先 n % k == 0
(b) sum[k - 1], sum[2 * k - 1], sum[3 * k - 1],....sum[n - 1] 严格递增，注意这个数列有n / k项。
所以我们循环k有n次真正判断额外的循环次数是n / k。 于是总的时间复杂度是n + (n的所有约数和）。
从wikipedia看到
约束和的复杂度是O(nloglog(n)))的，所以时间复杂度就是这样了。
其实只要稍加改进时间复杂度可以达到O(n)。
考虑距离最远的连个山峰，设最大距离为D，（第一个山峰到开头的距离，以及最后一个山峰到末尾的距离都算进去），则如果桶的size >= D，则一定可以。size < D / 2一定不可以。所以我们只要看D/2..D之间的n的约数即可。如果这里没有解，再沿着D向上找一个约数（但是不用再验证）。之所以把第一个山峰和最后一个山峰那块都算进去是因为可以保证第一个桶和最后一个桶不空。然后可以轻松得出上述结论。
复杂度分析，令m = D / 2。则 复杂度只有n / m + n / (m + 1) + ... + n / D，每一项不大于n / m，一共m项，所以时间复杂度居然是O(n)。
int solution(vector<int> &A) {
// write your code in C++98
// 2 * size - 1 >= D
// size < D
int n = A.size();
if (n <= 2) {
return 0;
}
vector<int> sum;
sum.resize(n);
int last = -1, D = 0;
sum[0] = 0;
for (int i = 1; i + 1 < n; ++i) {
sum[i] = sum[i - 1];
if ((A[i] > A[i - 1]) && (A[i] > A[i + 1])) {
D = max(D, i - last);
last = i;
++sum[i];
}
}
if ((sum[n - 1] = sum[n - 2]) == 0) {
return 0;
}
D = max(D, n - last);
for (int i = (D >> 1) + 1; i < D; ++i) {
if (n % i == 0) {
last = 0;
int j;
for (j = i; j <= n; j += i) {
if (sum[j - 1] <= last) {
break;
}
last = sum[j - 1];
}
if (j > n) {
return n / i;
}
}
}
for (last = D; n % last; ++last)
;
return n / last;
}
http://www.cnblogs.com/lautsie/p/4110313.htmlhttps://github.com/yiqin/Codility-Practice/blob/master/Peaks.java
Read full article from Codility and other programming lessons: Lesson 8: Peaks (Peaks)
