0

假设您有一个整数数组，例如：[0,1,2, 5,6,7, 9,10,11]。在理想的世界中，它们会被排序，但如果算法可以在未排序的情况下工作，那就更好了。

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

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

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

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

有任何想法吗？

4

1 回答 1

0

我想出了这个算法（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-24T00:30:18.920 回答