给定范围内最长连续1的查找频率[关闭]

Question

关闭。这个问题需要更多focused。它当前不接受答案。

---

是否要改善此问题？更新问题，使其仅按editing this post专注于一个问题。

关闭19分钟前。

我想在给定范围内的数组中找到最长连续1个的频率。例：`

arr = {1,1,0,0,1,1,1,0,0,1,1,1}} range（L，R）=（3,11）{从0开始的索引}`

因此，连续1的最大长度为3 {1,1,1}而给定范围内的频率为2。

约束：

2 <= n <= 10 ^ 51 <= q <= 10 ^ 5

n =数组大小

q =范围查询数

我有O（n ^ 2）的解决方案，但我需要更有效的解决方案。

Answer 1

问题看起来很琐碎：

int length = 0, count = 0, i = 0;
while (i < n) {
    while (i < n && seq[i] == 0) i++;
    if (i < n) {
        int start = i;
        while (i < n && seq[i] == 1) i++;
        int size = i - start;
        if (size > length) {
            length = size;
            count = 1;
        } else if (size == length)
            count += 1;
        }
    }
}

想法很简单：对于序列1的每个序列，如果序列较长，则将其更新长度并将计数设置为1，否则，如果长度相等，则递增计数器（如果长度较小，则不执行任何操作）。这只是对数据的一次传递：O（n），需要恒定的内存并且可以流式传输数据（不需要随机访问）。