如何找到数组中最长连续序列的长度？

Question

我正在尝试编写一个程序，返回重复数字的最长连续序列的整数长度值（例如，一个包含整数的数组如2、4、4、1、3、4、4、4、4、4、6、6、6将返回值5，因为5个4是最长的连续序列）。我已经尝试编写代码，但它总是返回数组中元素的总数。出了什么问题？

int length(int array[], int size)
{
   int x = 0, max;
   int result[size];

   for (int i = 0; i < size; i++)
   {
      x = i + 1;

      if (array[i] == array[x])
      {
         result[i] = x + 1;
      }

      if (result[i] > result[x])
      {
         max = result[i];
      }
   }

   return max;
}

- user2387766

---

作为提示 - 您可能希望跟踪当前计数和单独的“到目前为止最大计数”。如果需要更详细的答案，请告诉我。 - Amber

你需要一个数组来存储每个数字的计数，而不仅仅是一个特定的数字。 - Yu Hao

你可以对数组进行排序，如果整数范围较小，计数排序是一个不错的选择。 - nachokk

@Amber：我可以得到更详细的答案吗？ - user2387766

"出了什么问题？"——通过计算机播放...使用简短的示例逐步执行您的例程，您很快就会发现它无法解决问题。 - Jim Balter

Answer 1

这段代码考虑了一系列连续的整数，并返回最大的连续长度。

int length(int array[], int size) {
   int max = 1;
   int current = 1;
   int i;

   for (i = 1; i < size; i++) {
      if (array[i - 1] == array[i]) {    /* the run continues */
          current++;
          max = current > max ? current : max;
      } else {    /* the run was broken */
          current = 1;
      }
   }
   return max;
}

- Prashant Kumar

---

谢谢！简短问题，为什么 n 被设置为数组的第一个元素？我们不能这样说吗：如果（数组[i] == 数组[i + 1]）？为什么我们在 else 语句的最后一部分说：n = 数组[i]？ - user2387766

我想我的变量注释得不是很好。我使用“n”来表示当前的数字。 - Prashant Kumar

假设数组已排序...这是一个事实，但判断它是否已排序超出了提问者的专业水平，因此重要的是要说明。请注意，thejh已经给出了一个在已排序数组上操作的答案...并且已经这样说了。（但这段代码更好一些。） - Jim Balter

实际上很好的调用。n并不是必需的。我已经重构了代码并将其删除了。 - Prashant Kumar

非常感谢您的帮助！我认为这是我能够理解的最清晰/最简单的答案。 :) 但是感谢所有帮助过我的人！我很感激。 :) - user2387766

我在我的帖子中声明它考虑整数的运行。这也符合OP在修订后的问题中给出的条件。 - Prashant Kumar

Answer 2

就像 nachokk 所说的那样，首先对值进行排序。之后，您可以像这样做：

int max(int a, int b) { return a>b ? a : b; }

int get_highest_repetitition_length(int arr[], int arr_len) {
  int len = 0, highest_len = 0;
  for (int i=0; i<arr_len; i++) {
    if (i>0 && arr[i-1] != arr[i]) {
      highest_len = max(len, highest_len);
      len = 0;
    }
    len++;
  }
  highest_len = max(len, highest_len);
  return highest_len;
}

- thejh

---

有没有一种方法可以在不先排序值的情况下完成这个任务？而且我不能使用max()函数。 :( 顺便说一句，这不是作业，我只是在练习。 :) - user2387766

@Karen：我可以想到一种简单的方法，不需要排序，但是时间复杂度会非常糟糕，达到了O(n^2)。另外，如果你愿意，可以将highest_len = max(len, highest_len);替换为if (len > highest_len) highest_len = len;或其他什么方式。 - thejh

@Karen 如果这不是作业的话，那是谁不允许你使用max函数呢？请注意，这个答案提供了自己的max函数...你不能写函数吗？不能写名为max的函数吗？不能写一个找到两个参数中最大值的函数吗？我不知道你所面临的限制是哪一个，但是这些限制都是没有意义的，与编程技术无关。至于不使用排序的方法：当然可以，但是它们将需要一个查找表来映射整数和它们的计数（除非查找本身是O(nn)，否则不需要O(nn)）。 - Jim Balter

哦，这个问题要求我为解决方案编写一个单一的函数。 - user2387766

@Karen 那么问题就在于需要不良的编程实践...我建议寻找更好的问题来源。 - Jim Balter

Answer 3

希望这可以帮到你。如果你想要在不排序的情况下得到结果，你需要知道输入中数字的范围。假设范围是从[0 , size)。

int get_max_rep(int array[], int size) 
{
int* counter = (int *)malloc(sizeof(int)*size);    
// initialize
for (int i = 0; i < size; ++i) {
  counter[i] = 0;
}

int max = 0;
for (int i = 0; i < size; ++i) {
  ++counter[array[i]];
  if(max < counter[array[i]])
    max = counter[array[i]];
}
free(counter);
return max;
}

如果范围是[a，b)，其中a < b，则需要进行一些额外的工作。此外，如果数组counter的大小成为问题，则可以使用位向量作为替代方案。

- A. K.

---

不，你不需要知道数字的范围...尤其是在你的代码所使用的语言不是C语言的情况下，因此这个答案为-1。 - Jim Balter

很抱歉使用new/delete。然而，我仍然认为，为了正确计算最大重复数字，需要知道数字范围。 - A. K.

那么没有可变大小的容器吗？C++中没有vector或C中的realloc吗？ - Jim Balter

事实证明，这是一个解决与OP原意不同的问题的方案。 - Jim Balter