从整数创建间隔

Question

我正在寻找创建“Interval”（时间间隔）的有效方法。

Interval - (startIndex [inclusive], endIndex [exclusive])

从未排序的整数数组中选取。

例如，

Array A - [3, 1, 8, 5, 11, 10, 2]

应该生成一个由Interval组成的有序列表。

ordered-List - [(1, 4), (5, 6), (8, 9), (10, 12)]

我的初步想法是对此进行排序，然后从左到右扫描，创建区间，了解下一个元素不连续的地方。

我们能否使用修改过的区间树概念以线性时间完成这个过程，或者有更好的方法吗？

PS：我可以接受O(N)空间复杂度。

提前感谢您。

---

编辑：由于我的范围在[0:1000]之间，并且每次的元素数量不应超过1000，因此我按照排序的方式进行了处理，但我仍然看到改进的机会。以下是我的代码：

private class Interval {
    private final int startIndex; // inclusive
    private final int endIndex; // exclusive

    private Interval(int startIndex, int endIndex) {
        Validate.isTrue(startIndex >= 0, "start-index (0-based): " + startIndex + ",  is lesser than 0.");
        Validate.isTrue(startIndex < endIndex, "start index " + startIndex + ", is out of bound with respect to end index " + endIndex + ".");
        Validate.isTrue(endIndex <= numberOfSlides(), "end index " + endIndex + ", points to slide that doesn't exist.");

        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    private int getRange() {
        return this.endIndex - this.startIndex;
    }

    private int startIndex() {
        return this.startIndex;
    }
}

private List<Interval> createIntervals(int[] slideIndexes) {
    Validate.notNull(slideIndexes, "The array of slide indexes is null!");
    Validate.isTrue(slideIndexes.length != 0, "The array of slide indexes is empty!");
    final List<Interval> intervals = new ArrayList<>();
    Arrays.sort(slideIndexes);        
    int curStart = slideIndexes[0], lastLink = curStart + 1;
    for (int i = 1; i < slideIndexes.length; i++) {
        if (slideIndexes[i] == lastLink - 1) { // handles duplicates!
            continue;
        } else if (slideIndexes[i] != lastLink) {
            intervals.add(new Interval(curStart, lastLink));
            curStart = slideIndexes[i];
        }
        lastLink = slideIndexes[i] + 1;
    }
    intervals.add(new Interval(curStart, lastLink));

    return intervals;
}

- unknown_boundaries

---

你试过你的想法吗？另外，如果你使用Guava，你可以使用Range。 - fge

你对 O(n) 没问题吧？我认为这是最小的复杂度，因为你肯定需要扫描数组。你尝试过扫描空隙吗？也许你应该发一下你的尝试。 - Stefan

@PhamTrung，元素可能在50到1000之间。 - unknown_boundaries

数组中是否可能存在重复项？ - Sildoreth

@Sildoreth 哦，我还没有考虑过那个。理想情况下不应该有任何重复的，但如果出现了，我可能需要删除它们，或者不予处理。 - unknown_boundaries

Answer 1

如果数组A中每个元素的值较小，我们可以使用频率表fre来标记A中各元素的出现频率。

int[]fre = //
for(int i : A)
   fre[i]++;

在此之后，您可以将旧算法应用于数组 fre 以创建这些间隔。

for(int i = 50; i <= 1000; i++){
    if(fre[i] == 0){
       //Do something
    }else{
       //Do other thing
    }
}

这个算法的时间复杂度为O(max(n, 1000))，其中n是A中元素的数量。

- Pham Trung

---

如果数组是[3, 1, 8, 5, 11, 10, 2, 1000]，那么我需要创建额外的哈希数组[1-1000]，其中大多数值将是稀疏的。这不错，但空间不是O(N)，而是取决于数组中的最大/最小值，再次查找最小值和最大值是一次遍历。也许我想太多了，因为问题在元素方面并不大。 - unknown_boundaries

@Prakhar 如果 n log n > 1000，则可以使用此算法，并针对 n 小的情况使用旧算法。我认为，当 n < 1000 时，O(n) 或 O(n log n) 解决方案没有太大的差异。 - Pham Trung

这就是我所思考的，也许我为这个问题想得太多了。不管怎样，感谢你的解决方案。 - unknown_boundaries

Answer 2

在一般情况下，除非使用额外的空间与最高价值项成比例，否则您可能无法做得比O(n log n)更好，如Pham Trung算法所示，它基本上是一种计数排序。

为未排序的项目创建一组连续区间本质上是一种排序算法。例如，想象一下，您的项目列表是[7,0,3,9,8,4,5,2,1,6]。那就是单个闭合区间（0,10）。如果您能在不使用额外内存的情况下以少于O(n log n)的时间计算出它，则可以在少于O(n log n)的时间内对任意数组进行排序。但我们已经知道比较排序的下限是O(n log n)。

假设你知道数组中只包含一个闭区间，那么如果你知道最小值和最大值，可以在线性时间内对其进行排序。但如果你不知道数组中项所代表的区间数量，则要么使用非比较排序（计数排序、基数排序等），需要至少与N成比例的额外空间，要么进行比较排序。

- Jim Mischel

Answer 3

我会这样做：

1. 使用快速排序算法对列表进行排序

   • 我建议使用 归并排序, 堆排序 或者 快速排序
2. 遍历排序后的列表，处理非连续的情况

是的，这将给你一个 O(n log n) 的运行时间。但除非你期望数组非常巨大——比如有 100 万个元素或更多——否则这不应该成为问题。最终，这种方法应该足够快。

值得一提的是，一天中甚至没有 100 万秒：(24 小时) * (60 分钟/小时) * (60 秒/分钟) = 86400 秒。我不知道这是否适用，但你正在使用一个名为“Interval”的类，这往往暗示着“时间”。

- Sildoreth

---

如果列表很大，那么您的先排序再分组的方法将是唯一合理的方法，因为任何其他解决方案都需要使用至少O(N)额外的空间。 - Jim Mischel

@JimMischel 我可以接受 O(N) 的空间复杂度。 - unknown_boundaries