Here is compact linear solution (it is based on some non-trivial
observations):
int min = 0, p = 1, l = 0;
while (p < n && min + l + 1 < n) {
int cmp = buffer[min + l] - buffer[(p + l) % n];
if (cmp == 0)
++l;
else if (cmp < 0) {
p += l + 1;
l = 0;
}
else {
min = max(min + l + 1, p);
p = min + 1;
l = 0;
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
