在排序数组中创建区间

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

实际上我有更大的数据，所以我需要一个具有良好运行时间的算法。

我的想法如下：将数组分成两部分，并用 4 个循环遍历数组。从 0 索引开始一个循环，从数组中间开始 2 个循环，从数组末尾开始 1 个循环。每个循环都会检查当前元素和下一个元素的差异是否为 1，如果是，则转到下一个元素，否则从之前的元素创建一个间隔，并从下一个元素开始一个新的间隔。

我的问题是这是一个好方法，还是有更好的方法？请伪造或 java 代码。

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]);

可运行版本：https://ideone.com/NZ2Uex

Answer 2

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

是的，它需要第 3 方库，但毕竟是 Apache Commons。

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;

您可以轻松地适应 arrays 通过获取间隔并在每个间隔之后复制。

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

在排序数组中创建区间

Create intervals in a sorted array

java

intervals

sortedlist