用於創建<code>Interval</code>創建一個從整數

Question

我在尋找有效的方法間隔，

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

從 unsorted integer array

。

例如，

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

應導致ordered list的Interval

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

在我最初的想法是排序這和掃描從左至右創建理解區間下一個元素不連續。

我們可以使用修改的Interval Tree概念在線性時間內做到這一點，還是有更好的方法來做到這一點？

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; 
} 

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數量。

Answer 2

在一般情況下，您可能無法比O（n log n）做得更好，除非您使用與最高價值項目成比例的額外空間，如Pham Trung的算法所示，該算法基本上是counting sort。

爲未排序的項目列表創建一組連續間隔的核心是排序算法。例如，假設您的項目列表是[7,0,3,9,8,4,5,2,1,6]。這是單閉區間（0,10）。如果可以在不使用額外內存的情況下計算小於O（n log n）的時間，那麼您可以在小於O（n log n）時間內對任意數組進行排序。但是我們已經知道comparison sorting has a lower bound of O(n log n)。當然，如果你知道你的數組包含一個單獨的閉區間，那麼如果你知道最小和最大值，你可以用線性時間對它進行排序。但是，如果您不知道數組中的項目有多少間隔，那麼您最終將使用非比較排序（計算排序，基數排序等），並且至少與N成比例的額外空間，否則比較排序。

Answer 3

我會做的方式是：

1. 使用快速排序算法進行排序列表第一

   • 我建議，要麼MergeSort，HeapSort，或QuickSort
2. 循環排序列表 - 如您所說 - 並說明非連續的情況

是的，這會給你一個O（n log n）的運行時間。但是，除非你期望陣列超大 - 像100萬個或更多元素 - 這應該不成問題。最終，這種方法應該足夠快。

值得一提的是，一天不會有100萬秒：(24 hours) * (60 mins/hour) * (60 secs/min) = 86400 seconds。我不知道這是否適用，但你是使用名爲「間隔」，這往往暗示在「時間」的類。