我想在给定范围内的数组中找到最长连续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。
我有O(n ^ 2)的解决方案,但我需要更有效的解决方案。
问题看起来很琐碎:
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),需要恒定的内存并且可以流式传输数据(不需要随机访问)。