对数组中连续数字的片段或序列进行计数

Question

假设你有一个整数数组，例如: 0,1,2，5,6,7，9,10,11。在理想的情况下，它们应该是排序的，但如果算法可以处理未排序的，那就更好了。

我需要知道这个组中有多少个“片段”。想象一下，数组由一个文件的字节数组组成；这个文件有多零碎？

在上面的例子中，我计算了3个组/片段。

我的目标是将磁盘上的“文件”总数相加，然后是“碎片”的总数，然后计算碎片(我认为是1 - (files / fragments)。10个文件，10个碎片= 0%碎片-但是，如果每个文件被分成两个，生成20个碎片，则bd 50%碎片)。

因此，我正在寻找的算法需要查看整数数组，并计算出有多少个连续的数字组。

有什么想法吗？

Answer 1

我想出了这个算法(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时，就会增加一个计数器。