Given a sorted array in non-descending order, the element type can be positive integer or char, return the length of the longest consecutive segments
Example,
Input:"1223334556", output 3
Input: "abccdef", output 2
This problem is call the Plateau problem, and it has once confused the famous computer scientistDavid Gries
Here is a solution
for ( int i = 0 ; i < s.Length; i ++ )
{
if (s[i] == s[i - length])
length ++ ;
}
return length;
the idea is that, first let length = 0;
than increase length when the next char is same as the start char, suppose you are start at index i, and length = 0, it is obviousely s[i] == s[i – length]; since any char equals to itself.
then if the char at position i + 1 equals to current char,increase the length by 1, else do nothing.
Note that, the given string must be in non-descending order, otherwise, this method will not work.
Take a look at the example below
"11212", you will get the result 3, but not 2, why?
When you move to the first ‘2’, the condition in the if statement is false, and current length is 2, since there are two consecutive 1s in the front of the string, then you move to the last 1, and this time the if condition is true,since the second 1 equals to the last 1, and you got length increased by 1, thus the result is 3, and that’s a incorrect result. This was all caused by the given string which was not in non-descending order.
The time complexity of above code is O(n), where n is the length of the given string.
The following code is performs a little better, which has a complexity of O(n – maxLen), where maxLen is the length of the longest consecutive segment in the given string.
Code
How about remove the condition, let the array in any order, for example 11212, returns 2, not 3
We can record the current length, and define another variable maxLen to hold the final result, each time we met the different char, let curLen = 0, and count the next loop. else, increase curLen, and update maxLen if it greater than maxLen.
code like
Code
and further more, if i want to return the longest consecutive string
you should use another int to record the position when the index stop increasing.
Code
本文转自zdd博客园博客，原文链接：http://www.cnblogs.com/graphics/archive/2009/06/06/1497515.html，如需转载请自行联系原作者
