我有一个有序std::vector<int> ，我想找到在这个载体上最长的“连续编号的连胜”，然后返回它的长度和在连胜的最小数目。
为了形象化为你：假设我们有： 1 3 4 5 6 8 9
我想它返回： maxStreakLength = 4和streakBase = 3
可能有机会在那里将有2条痕，我们要选择哪一个是更长的时间。
什么是最好的（最快）的方式来做到这一点？ 我试图实现这一点，但我有问题与向量中的一个以上的连胜应对。 我应该使用临时向量，然后比较它们的长度？
Answer 1:
不，你可以在一个穿过载体和唯一保存最长的起点和长度迄今发现做到这一点。 您还需要比“N”比较少得多。 *
提示：如果你已经有说4长的比赛在5号位结束（= 6），你有哪个位置旁边的检查？
[*]留给读者做练习，以制定出什么是可能的O（）复杂;-)
Answer 2:
看是否事实数组进行排序，可以以某种方式利用来提高算法这将是有趣。 浮现在脑海的第一件事情是这样的： 如果你知道输入阵列中的所有号是唯一的 ，那么对于一个范围的元素[i, j]数组中，你可以立即告诉该范围内的元素是否是连续的还是不，实际上并没有翻翻范围。 如果这个关系成立
array[j] - array[i] == j - i
那么你可以立刻说，在这个范围内的元素是连续的。 这个标准，显然，使用该数组进行排序，而且数字不重复的事实。
现在，我们只需要开发一种算法，将采取标准的优势。 这里是一个可能递归方法：
- 递归步骤的输入是元件的范围
[i, j]最初，它是[0, n-1]-整个阵列。 - 应用上述准则范围
[i, j]如果该区域原来是连续的，没有必要进一步进行细分。 发送至输出（参见下文进一步的详细信息）。 - 否则（如果范围是不连续的），将其分成相等的两个部分
[i, m]和[m+1, j]。 - 递归调用在下部的算法（
[i, m]然后在上部（[m+1, j]）。
上述算法将执行阵列和使用所述左第一方法中，划分树的递归下降的二进制分区。 这意味着，该算法会发现在左到右的顺序连续元素相邻子范围。 所有你需要做的是相邻子区域连接在一起。 当您收到一个小范围[i, j]这是在步骤2“发送到输出”，你就与先前接收的子范围来连接它，如果他们确实是连续的。 或者你必须开始一个新的范围内，如果它们是不连续的。 在这期间你有跟踪迄今为止发现的“最长连续范围”的。
而已。
该算法的好处是，它能够检测到“早期”连续元素的子范围，如果没有这些子范围内寻找。 显然，这是最坏的情况下的性能（如存在不连续的子范围的话）仍然O(n) 在最好的情况下，当整个输入数组是连续的，该算法会立即检测到它。 （我仍在为这个算法有意义Ø估计。）
该算法的可用性，再次，由唯一性要求破坏。 我不知道是否是东西是你的情况“给予”。
总之，这里是一个可能的C ++实现
typedef std::vector<int> vint;
typedef std::pair<vint::size_type, vint::size_type> range;
class longest_sequence
{
public:
const range& operator ()(const vint &v)
{
current = max = range(0, 0);
process_subrange(v, 0, v.size() - 1);
check_record();
return max;
}
private:
range current, max;
void process_subrange(const vint &v, vint::size_type i, vint::size_type j);
void check_record();
};
void longest_sequence::process_subrange(const vint &v,
vint::size_type i, vint::size_type j)
{
assert(i <= j && v[i] <= v[j]);
assert(i == 0 || i == current.second + 1);
if (v[j] - v[i] == j - i)
{ // Consecutive subrange found
assert(v[current.second] <= v[i]);
if (i == 0 || v[i] == v[current.second] + 1)
// Append to the current range
current.second = j;
else
{ // Range finished
// Check against the record
check_record();
// Start a new range
current = range(i, j);
}
}
else
{ // Subdivision and recursive calls
assert(i < j);
vint::size_type m = (i + j) / 2;
process_subrange(v, i, m);
process_subrange(v, m + 1, j);
}
}
void longest_sequence::check_record()
{
assert(current.second >= current.first);
if (current.second - current.first > max.second - max.first)
// We have a new record
max = current;
}
int main()
{
int a[] = { 1, 3, 4, 5, 6, 8, 9 };
std::vector<int> v(a, a + sizeof a / sizeof *a);
range r = longest_sequence()(v);
return 0;
}
Answer 3:
我认为，这应该这样做？
size_t beginStreak = 0;
size_t streakLen = 1;
size_t longest = 0;
size_t longestStart = 0;
for (size_t i=1; i < len.size(); i++) {
if (vec[i] == vec[i-1] + 1) {
streakLen++;
}
else {
if (streakLen > longest) {
longest = streakLen;
longestStart = beginStreak;
}
beginStreak = i;
streakLen = 1;
}
}
if (streakLen > longest) {
longest = streakLen;
longestStart = beginStreak;
}
Answer 4:
你不能在不到解决这个问题的O(N)时间。 想象列表是所述第一N-1的偶数，加上单个奇数（从第一选自N-1的奇数）。 再有就是在列表长度3某处的一个连胜，但你需要扫描整个列表中找到它最糟糕的情况。 即使在平均您需要检查列表中至少有一半找到它。
Answer 5:
类似罗德里戈的解决方案，但解决您的例子还有：
#include <vector>
#include <cstdio>
#define len(x) sizeof(x) / sizeof(x[0])
using namespace std;
int nums[] = {1,3,4,5,6,8,9};
int streakBase = nums[0];
int maxStreakLength = 1;
void updateStreak(int currentStreakLength, int currentStreakBase) {
if (currentStreakLength > maxStreakLength) {
maxStreakLength = currentStreakLength;
streakBase = currentStreakBase;
}
}
int main(void) {
vector<int> v;
for(size_t i=0; i < len(nums); ++i)
v.push_back(nums[i]);
int lastBase = v[0], currentStreakBase = v[0], currentStreakLength = 1;
for(size_t i=1; i < v.size(); ++i) {
if (v[i] == lastBase + 1) {
currentStreakLength++;
lastBase = v[i];
} else {
updateStreak(currentStreakLength, currentStreakBase);
currentStreakBase = v[i];
lastBase = v[i];
currentStreakLength = 1;
}
}
updateStreak(currentStreakLength, currentStreakBase);
printf("maxStreakLength = %d and streakBase = %d\n", maxStreakLength, streakBase);
return 0;
}
文章来源: What is the fastest way to find longest 'consecutive numbers' streak in vector ?
