algorithm - 采访 : Find Ranges of All Consecutive Numbers

Question

给定一个排序数组，其中包含一些序列号和一些非序列号。编写一个算法，将此数组作为输入并返回所有连续数字的 {start, end} 列表。连续数字仅相差 1。

例如数组:

[4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27]

public class Range
{
    private int begin;
    private int end;
    public int begin { get; set; }
    public int end { get; set; }
}

这里的 O(n) 解决方案似乎很明显，但有没有办法在更短的时间内完成？

Answer 1

一个解决方案是一次说出 3 个数字并查看它们之间的差异

如果差值等于3那么它们是连续的，然后再向前移动3，直到你发现差值不是3，然后你向后移动一步，如果差值是2则结束范围并且从我们有差异的前一个数字开始您的下一个范围。

在最坏的情况下，根本没有连续的数字，对于大 N，我们将迭代 n/3 次，这很重要。

编辑:

这种方法最糟糕的情况是当有两个连续的数字对时，我们需要接触所有数字，所以在这种特殊情况下它将是 O(n)。