假设我们有一个像 [6,5,4,7,3] 这样的数字列表。我们如何判断数组是否包含连续的数字？一种方法当然是对它们进行排序，或者我们可以找到最小值和最大值。但是我们可以根据元素的总和来确定吗？例如，在上面的示例中，它是 25。有人可以帮我解决这个问题吗？
问问题
1056 次
2 回答
3
元素的总和本身是不够的。
相反，您可以检查：
- 所有元素都是独一无二的。
或者：
- 最小值和最大值之间的差异是正确的
或者
- 所有元素的总和是正确的。
方法一
对列表进行排序并检查第一个元素和最后一个元素。
通常这是 O(n log(n))，但如果您的数据集有限，您可以使用计数排序或基数排序在 O(n) 时间内排序。
方法二
传递数据以获得最高和最低元素。
当您通过时，将每个元素添加到哈希表中，并查看该元素现在是否已添加两次。这或多或少是 O(n)。
方法 3
为了节省存储空间（哈希表），请使用近似方法。
传递数据以获得最高和最低元素。
正如您所做的那样，实施一种算法，该算法将以高（读取用户定义）概率确定每个元素是不同的。存在许多这样的算法，并且正在数据挖掘中使用。这是描述不同方法的论文的链接。
于 2012-09-09T16:20:46.690 回答
0
如果数组的最大值和最小值之间的差等于 n-1，则数组中的数字将是连续的，前提是数字是唯一的（其中 n 是数组的大小）。当然，最小和最大数量可以在 O(n) 中计算。
于 2012-09-09T16:01:45.547 回答