計算數組中的片段或連續數字的序列

假設您有一個整數數組，例如：[0,1,2,5,6,7,9,10,11]。在理想的世界中，他們將被排序，但是如果算法可以與未排序的一起工作，甚至更好。計算數組中的片段或連續數字的序列

我需要知道這個組中有多少「片段」。想象一下，數組構成一個文件的字節數組;這個文件有多碎片？

在上面的例子中，我計數3組/片段。我的目標是將一個磁盤上的「文件」總數加起來，然後計算碎片的總數，然後計算碎片（1 - (files/fragments)，我認爲.10個文件，10個碎片= 0％碎片 - 然而，如果每個文件被分成兩部分製作20個片段，那將會產生50％的碎片）。

所以我正在尋找的算法需要看一個int數組，並計算出有多少個連續的數字組。

任何想法？

來源

2014-01-24 Nick

想到'範圍樹'或'區間樹'。 GIYF – wildplasser

Wildplasser - 謝謝，我會看看那些。我已經搜索了相當廣泛的搜索結果。我發現了類似的問題，但沒有一個符合我的要求。 – Nick

它可以通過散列表加速（並查找L和R neigbors） – wildplasser

我想出了這個算法（的ObjectiveC）...

-(NSInteger) numberOfFragments { 
    NSInteger fragments = 1; 

    NSArray *sortedBytes = [_bytes sortedArrayUsingComparator:^NSComparisonResult(GameFileByte *a, GameFileByte *b) { 
     return ([a bytePosition] < [b bytePosition]) ? NSOrderedAscending : ([a bytePosition] > [b bytePosition]) ? NSOrderedDescending : NSOrderedSame; 
    }]; 


    NSInteger lastBytePosition = -1; 
    for (GameFileByte *byte in sortedBytes) { 
     if (lastBytePosition > 0 && ((byte.bytePosition - lastBytePosition) > 1)) { 
      fragments++; 
     } 
     lastBytePosition = byte.bytePosition; 
    } 


    return fragments; 
}

這似乎爲我工作...它保證了字節是在正確的順序，然後通過他們循環，增加計數器每當當前字節離開它的前輩超過1。

來源

2014-01-24 00:30:18 Nick

計算數組中的片段或連續數字的序列

回答

相關問題