在已排序的数组中创建间隔

Question

假设我有一个已排序的数组{1, 2, 3, 4, 5, 7, 8, 9, 10, 15, 16, 21, 23, 25, 26}。我想按以下方式将这些元素放入区间中：

1..5
7..10
15..16
21..21
23..23
25..26

实际上，我的数据量很大，因此我需要一个运行时间较好的算法。

我考虑的是以下方法：将数组分成2部分，并用4个循环遍历数组。第1个循环从0索引开始，第2个循环从数组中间开始，第3个循环从末尾开始，每个循环都会检查当前元素和下一个元素之间的差是否为1，如果是，则继续到下一个元素，否则从前面的元素创建一个区间，并从下一个元素开始创建新的区间。

我的问题是这是否是一种好的方法，还是有更好的方法？请提供伪代码或Java代码。

- wfmn17

---

为什么不直接从索引0开始进行顺序循环，并跟踪间隔的第一个元素呢？ - tsolakp

你是如何推导出这些间隔的？我没有看出任何规律。 - user3437460

为什么要用这么多循环？似乎只需要一个循环，当上一个值 + 1 不等于当前值时，就开始一个新的间隔。 - Andrew S

你是否已经获得了区间？你是否正在尝试编写一个函数，该函数以int[] originalArray和int[][] intervals（其中对于所有i < intervals.length，intervals[i].length == 2）作为参数？请澄清输入的数据类型以及期望的输出数据类型。此外，您是否已经尝试编写过这个方法？您能分享一下您所做的吗？ - Blake

@Blake 输入为int[]类型的数组，其中包含000006到999999之间的数字。输出可能为int[][]类型。 - wfmn17

Answer 1

线性解决方案：

int intervalStart = a[0];
for (int i = 1; i < a.length; ++i) {
    if (a[i] > a[i-1] + 1) {
        outputInterval(intervalStart, a[i-1]);
        intervalStart = a[i];
    }
}
outputInterval(intervalStart, a[a.length-1]);

Runnable version: https://ideone.com/NZ2Uex

- DAle

Answer 2

你可以考虑使用Apache Commons中的IntRange数组来表示这样的概念。

是的，这需要使用第三方库，但毕竟它是Apache Commons。

- nasukkin

Answer 3

你正在尝试获取连续整数列表。

在O(n)中最简单和最朴素的方法是像这样做：

List<List<Integer>> list_of_sublists = new List<>(); // The list of sublists
int lastElement = elements[0];
List<Integer> subList = new List <>(); // The current sublist
subList.add(lastElement);
int i = 1; // We start with index 1 because index 0 is already done
while (i < elements.length){
   int element = elements[i]
   if !(lastElement + 1 == element)){ //If not a consecutive we start a new list
       list_of_sublists.add(subList);
       subList = new List<>();
   }
   lastElement = element;
   subList.add(element);
   i ++;

//We didn't add the last sublist
list_of_sublists.add(subList);
return list_of_sublists;

你可以通过获取间隔并在每个间隔之后复制来轻松适应 数组。

- µTheory

Answer 4

另一种版本，使用两个指针（Python）：

def compress_to_range(vector):
    # O(n) in time, just one pass thru the list
    result = []
    i = 0
    while i < len(vector):
        j = i+1
        while j < len(vector) and vector[j] == vector[j-1]+1:
            j += 1
        # j now points to the element outside the interval
        result.append([vector[i], vector[j-1]])
        i = j

    return result

- milan