我正在寻找一种高效的算法来查找二进制字符串中最长的零序列。我的实现是在Python 2.7中，但我只需要算法的思路。
例如，对于给定的 '0010011010000' 字符串，函数应该返回 4。
7个回答
8
我认为没有比一次遍历字符串更好的方法了，可以边计算当前序列长度（并更新最大值），边遍历。
如果你所说的“二进制字符串”是指原始位，你可以每次读取一个字节，并提取其中的八个位（使用位移或掩码）。 这不会改变整体算法或其复杂度。
- Thilo
8
如果您事先知道属性，例如如果您事先知道总长度并且已经找到一个大于剩余数字的字符串（终止），那么可能有一些快捷方式可用，但我认为您无法做得更好。 - Alex T
1@Soke 这种方法需要
O(1) 的空间和 O(n) 步骤。我认为它非常高效，而且我怀疑你在不对输入字符串提出其他要求的情况下无法更快地完成它。 - Konstantin1您可以将其并行化（如果字符串足够大以使这种方法有意义）：对字符串进行分区，对于每个分区返回最长链的长度、最长前缀和最长后缀。 - Thilo
如果它是一个二进制数（我认为你说“原始位”时指的就是这个），那么有一些位操作技巧可以用来改善平均情况下O(n)复杂度。但最坏情况（交替出现0和1）仍然是O(n)。我相当确定OP是在询问一个
str类型。 - John La Rooy@John，我怀疑你指的是运行时间而不是复杂度。我想不出任何位操作的小技巧可以让你不检查每个字节，所以它仍然是
O(n/8)（是的，我知道这种“野兽”不存在），也就是O(n)。 - paxdiablo显示剩余3条评论
2
可以打败显而易见的算法。这个想法是，如果你已经有一个长度为N的0序列，并且你看到两个1在不超过N个位置之内，你就不需要检查中间的任何位置。因此，从末尾而不是从开头检查候选的零序列。最坏的情况下，你将检查所有元素，就像天真的方法一样，但平均来说，它会比那少。
所以算法如下（伪代码，未经测试）
maxrun = 0
curpos = 0
runstart = 0
runend = 0
while curpos + maxrun < array.length
broken = false
for i = curpos + maxrun, i >= curpos and not broken, --i
if array[i] == 1
broken = true
curpos = i + 1
if not broken
runstart = curpos
# found a longer run of 0s
# now extend it to the end
maxrun++
curpos += maxrun
while curpos < array.length and array[curpos] == 0
maxrun++
# ok found the 1 at the right end of the run
# go to the next position and start over
runend = curpos
curpos++
# the longest run of 0s is [runstart, runend)
- n. m.
2
已编译的正则表达式可能会相当快，但我还没有真正测试过。尽管如此：
>>> binstr = '0010011010000'
>>> import re
>>> zeros = re.compile(r'0+')
>>> max(len(m) for m in zeros.findall(binstr))
4
- Shashank
1
这有点凌乱，我知道如果再多想一下，就能改进结尾。
def solution(N):
y = [int(x) for x in bin(N)[2:]]
lst,zero = [],0
for r in y:
if r == 0:
zero +=1
else:
if zero > 0:
lst.append(zero)
zero = 0
try:
return max(lst)
except Exception as E:
return 0
你可能不需要最后一部分，只需返回 lst 中的最大值。
- Dean Welch
1
为了找到二进制字符串中最长的连续零序列，我建议按照以下步骤进行：
你应该单独处理二进制字符串以零结尾的情况。将其添加到提供的大纲中，你就完成了。
这种方法的复杂度与二进制字符串的长度成线性关系。
int maxConsecutiveZeros(String binaryString) {
int maxcount = Integer.MIN_VALUE;
int currcount = 0;
for(int i=0; i < binaryString.length(); i++) {
if(binaryString.charAt(i) == '0') {
currcount++;
} else {
maxcount = Math.max(currcount, maxcount);
currcount = 0;
}
}
return maxcount;
}
你应该单独处理二进制字符串以零结尾的情况。将其添加到提供的大纲中，你就完成了。
这种方法的复杂度与二进制字符串的长度成线性关系。
- Bhoot
2
他要求用Python... 这甚至不是伪代码... - Travis Griggs
粗体部分可以通过剪切和粘贴在2秒钟内完成。为什么不在您的“伪代码”中直接执行它呢？ - John La Rooy
1
这取决于你对“高效”的理解。
如果你的目的是尽量减少运行时间，你基本上需要逐个字符地遍历字符串，并分析连续零的运行情况，记录最长的一段，类似于以下方式：
def longRunZeros(s):
big = 0
curr = 0
for c in s:
if c == '0':
curr += 1
else:
if curr > big:
big = curr
curr = 0
if curr > big:
big = curr
return big
print longRunZeros('0010011010000')
如果你在谈论程序员的效率，只需要这样做：
def longRunZeros(s):
return max(len(i) for i in s.split('1'))
相反地。
它不一定是最快的，但它会让你有更多的时间，也许可以用来分析你是否需要这个操作的原始速度。由于代码长度，它几乎肯定不太容易出现错误。
至于你是否需要速度，请考虑以下情况。对于一个25M的字符串，采用逐字符方法进行100万次迭代需要2.826秒的CPU时间。相同工作量下，使用“split”方法需要3.186秒1。
因此，除非你的字符串比25M长得多，或者你需要做的次数比一百万次多得多，否则它不会有太大的区别，我倾向于选择对开发人员更容易的方法。
附言：在强调差异性能在这里是多么无关紧要之后，我感觉提到John La Rooy在评论中展示的另一种方法有点虚伪，因为它实际上似乎比我的两种方法都要快一些。
但是，为了完整起见，我将忍受指责并指出那个方法：
def longRunZeros(s):
return len(max(s.split('1')))
这似乎平均约为1.092，是上面逐字符情况速度的两倍。
1这些数字是在我的环境下进行五次运行的平均值，我不能保证它们在其他地方也能保持不变。
如果你曾经参与过优化工作，你应该知道应该在实际环境中进行测量，而不是依赖于互联网上某个随机（但极为好看）的人的话语 :-)
- paxdiablo
3
len(max(s.split('1'))) 在这个测试用例中也应该可以工作（相对于此计算机的 1280 纳秒，为 528 纳秒） - John La Rooy@John，那似乎比两种方法都要快得多。虽然我仍然认为这可能是不必要的微观优化，但出于完整性考虑，我已经包含了你更好的方法。 - paxdiablo
我认为我可以更容易地说服自己使用“max”的任一版本是正确的。如果可读性与足够快速相一致，那就是一个愉快的日子。 - John La Rooy
0
好的，正如有人提到的那样，如果类型是字符串，那么我认为你无法避免O（|N|）的I/O时间。我在这里只想说，如果它是一个整数，那么你可以做得更快一些，例如：
#include<bits/stdc++.h>
using namespace std;
int n;
void binary(int x){
if(x){
binary(x>>1);
if(x&1) putchar('1');
else putchar('0');
}
}
int main() {
scanf("%d", &n);
while(n){
binary(n);
puts("");
int x = log2(n&-n);
printf("Zero range: %d\n", x);
n >>= (x+1);
}
return 0;
}
忽略打印部分，我认为它的时间复杂度是O(lg N)？(注意：由于这里处理的是整数，不考虑填充零，但这应该不难)
- shole
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接