在数组中查找一定数量的相邻条目

Question

我正在 Java 中编写虚拟内存分配管理器。我在 n 条目上有一个布尔数组，需要在一行中找到一行 k 错误条目。除了进行大规模的二进制搜索并计算每批错误之外，是否有一种合适的方法来计算 k 错误，获取该行的起始索引。

谢谢！

Answer 1

如果 k 将占 n 的很大一部分，那么最简单的效率措施可能是在每次搜索中跳过 k 项。

int searchForFalses(boolean[] array, int k) {
    for (int n = 0; n < array.length; n += k) {
        if (!array[n])) {
            int start = n;
            while (start >= 0 && !array[start])
                start--;
            int end = n;
            while (end < array.length && !array[end])
                if (end - start >= k)
                    return start;
                else
                    end++;
        }
    }
    return -1;
}