4

我有一个排序std::vector<int>，我想在这个向量中找到最长的“连续数字条纹”，然后返回它的长度和条纹中的最小数字。

为您可视化它：假设我们有： 1 3 4 5 6 8 9

我希望它返回：maxStreakLength = 4和streakBase = 3

有时可能会有 2 个条纹，我们必须选择哪一个更长。

最好（最快）的方法是什么？我试图实现这一点，但我在处理向量中的多个条纹时遇到了问题。我应该使用临时向量然后比较它们的长度吗？

4

5 回答 5

7

不，您可以一次通过向量执行此操作，并且只存储迄今为止找到的最长起点和长度。您还需要比“N”个比较少得多。*

提示：如果您已经说在第 5 位 (=6) 结束的 4 长比赛，那么您接下来必须检查哪个位置？

[*] 留给读者作为练习，以计算出可能的 O( ) 复杂度；-)

于 2012-07-25T15:06:46.193 回答
3

看看是否可以利用数组已排序的事实来改进算法会很有趣。首先想到的是：如果您知道输入数组中的所有数字都是唯一的，那么对于数组中的一系列元素[i, j]，您可以立即判断该范围内的元素是否连续，而无需实际查看通过范围。如果这个关系成立

array[j] - array[i]  ==  j - i

那么您可以立即说该范围内的元素是连续的。显然，此标准使用了数组已排序且数字不重复的事实。

现在，我们只需要开发一种利用该标准的算法。这是一种可能的递归方法：

  1. 递归步骤的输入是元素的范围[i, j]。最初它是[0, n-1]- 整个数组。
  2. 将上述标准应用于 range [i, j]。如果范围是连续的，则无需进一步细分。将范围发送到输出（有关详细信息，请参见下文）。
  3. 否则（如果范围不连续），将其分成两个相等的部分[i, m]和[m+1, j]。
  4. 递归调用下部 ( [i, m]) 上的算法，然后在上部 ( [m+1, j]) 上调用算法。

上述算法将使用左优先方法执行数组的二进制分区和分区树的递归下降。这意味着该算法将以从左到右的顺序找到具有连续元素的相邻子范围。您需要做的就是将相邻的子范围连接在一起。当您收到[i, j]在步骤 2 中“发送到输出”的子范围时，如果它们确实是连续的，则必须将其与先前收到的子范围连接起来。或者你必须开始一个新的范围，如果它们不是连续的。一直以来，您一直在跟踪迄今为止发现的“最长连续范围”。

而已。

该算法的好处是它“早期”检测到连续元素的子范围，而无需查看这些子范围内。显然，最坏情况下的性能（如果根本没有连续的子范围）仍然是O(n). 在最好的情况下，当整个输入数组是连续的时，这个算法会立即检测到它。（我仍在为此算法进行有意义的 O 估计。）

该算法的可用性再次受到唯一性要求的破坏。我不知道在您的情况下这是否是“给定的”。

无论如何，这是一个可能的 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;
}
于 2012-07-25T16:54:28.690 回答
1

你不可能在短时间内解决这个问题O(N)。想象一下，您的列表是第一个N-1偶数，加上一个奇数（从第一个N-1奇数中选择）。然后在列表中的某处有一条长度为 3 的单条，但最坏的情况是您需要扫描整个列表才能找到它。即使平均而言，您也需要检查至少一半的列表才能找到它。

于 2012-07-26T05:11:44.673 回答
1

我相信这应该做吗？

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;
}
于 2012-07-25T15:06:58.347 回答
0

类似于 Rodrigo 的解决方案，但也解决了您的示例：

#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;
}
于 2012-07-25T15:36:32.267 回答