1

我有一个整数数组，我们从第三方提供商那里获得。这些是连续的，但由于某种原因它们错过了一个数字（抛出异常，它被吃掉并且循环继续丢失该索引）。这使我们的系统有些痛苦，我试图确保我们得到的数组确实是连续的。

这些数字从不同的偏移量开始（有时是 1000，有时是 5820，其他是 0），但无论从哪里开始，它都意味着从那里开始。

验证数组是否连续的最快方法是什么？尽管它现在看起来是一个必需的步骤，但我也必须确保它不会花费太长时间来验证。我目前从第一个索引开始，拿起数字并添加一个并确保下一个索引包含该等。

编辑：系统失败的原因是人们使用系统的方式可能并不总是按照最初选择的方式返回令牌 - 长篇大论。不幸的是，数据在到达我们的层之前无法更正。

4

4 回答 4

7

如果您确定数组已排序并且没有重复，您可以检查：

array[array.Length - 1] == array[0] + array.Length - 1
于 2011-03-24T00:22:34.993 回答
1

我认为在这里解决更大的问题是值得的： 如果数据不符合您的要求（顺序，没有间隙），您将怎么做？

如果您仍要处理数据，那么您可能应该投入时间使您的系统对数据中的空白或丢失条目更具弹性。

* *如果您需要处理数据并且它必须是干净的，您应该与供应商合作以确保他们向您发送格式正确的数据。

如果您要跳过处理并报告错误，那么断言没有间隙的前提条件可能是要走的路。在 C# 中，您可以做许多不同的事情：

  1. 如果数据已排序并且没有重复，只需检查LastValue == FirstValue + ArraySize - 1.
  2. 如果数据未排序但无重复，只需对其进行排序并执行上述操作。
  3. 如果数据没有排序，有重复并且你真的想检测差距，我会使用 LINQ。

List<int> gaps = Enumerable.Range(array.Min(), array.Length).Except(array).ToList();

或者更好（因为高端值可能超出范围）：

int minVal = array.Min();
int maxVal = array.Max();
List<int> gaps = Enumerable.Range(minVal, maxVal-minVal+1).Except(array).ToList();

顺便说一句，传递一个密集的、无间隙的整数数组的整个概念对于两方之间的接口来说有点奇怪，除非有一些额外的数据与它们相关联。如果没有其他数据，为什么不直接发送范围 {min,max} 呢？

于 2011-03-24T00:35:47.840 回答
0 
for (int i = a.Length - 2; 0 <= i; --i)
{
    if (a[i] >= a[i+1]) return false; // not in sequence
}
return true; // in sequence
于 2011-03-24T00:23:13.777 回答
0

如果对数组进行排序，Gabe 的方式绝对是最快的。如果数组未排序，那么最好对数组进行排序（使用合并/外壳排序（或类似速度的东西）），然后使用 Gabe 的方式。

于 2011-03-24T00:28:06.520 回答