什么是找到载体最长的“连续数”纪录的最快方法是什么？ [英] What is the fastest way to find longest 'consecutive numbers' streak in vector ?
问题描述
我有一个排序的的std ::矢量＆lt; INT＆GT; ，我想找到这个载体上最长的连续编号连胜，然后返回两者的长度它与最小号的条纹。
I have a sorted std::vector<int> and I would like to find the longest 'streak of consecutive numbers' in this vector and then return both the length of it and the smallest number in the streak.
要它想象为您提供：
假设我们有：
1 3 4 5 6 8 9
To visualize it for you :
suppose we have :
1 3 4 5 6 8 9
我想它返回： maxStreakLength = 4 和 streakBase = 3
有可能的场合里会有2条纹和我们要选择哪一个是更长的时间。
There might be occasion where there will be 2 streaks and we have to choose which one is longer.
什么是最好的（最快）的方式来做到这一点？我试图实现这一点，但我有问题，在载体多个连胜应对。我应该使用临时载体，然后比较它们的长度？
What is the best (fastest) way to do this ? I have tried to implement this but I have problems with coping with more than one streak in the vector. Should I use temporary vectors and then compare their lengths?
推荐答案
没有，你可以在一个穿过载体和唯一保存最长的起点和长度迄今为止发现做到这一点。您还需要比'N'比较少得多。 *
No you can do this in one pass through the vector and only storing the longest start point and length found so far. You also need much fewer than 'N' comparisons. *
提示：如果你已经有说4个长比赛结束在第5位（= 6）和哪个位置你必须检查下一个
hint: If you already have say a 4 long match ending at the 5th position (=6) and which position do you have to check next?
[*]留给读者的工作，以制定出什么是可能的O（）的复杂性; - ）
[*] left as exercise to the reader to work out what's the likely O( ) complexity ;-)
这篇关于什么是找到载体最长的“连续数”纪录的最快方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
