一个面试题，大家评评理

[gps949]

这两天去水了个面试，瞎写了一段代码，姑且不论这段代码能不能实现目标，面试现场 N 个面试官一位很牛逼哄哄地说：这个按理说 O(n)就可以了，你这两个遍历，都 O(n^2)了。
我简单解释两句说内层并不是完整遍历而是在计算连续 0 的长度后会把外层指针 i 移动过这一段，所以本质上还是近似算 O(n)的。
然后那个面试官又一脸不屑的说：你这两层遍历再怎么也不会是 O(n)，最多算 O(logn)，你回去再好好想想。
然后我无奈：好的。

下面是代码（只是近似，毕竟也没带出来材料）

a=[1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,0,1,0,1,0]
for (i=0;i<a.length;i++) {
    if (a[i]==0) {
        j=i+1;
        for (;j<a.length && a[j]==0;j++) {}
    
        //此处省略一通利用 i 和 j 的判断运算（没有对 i 或 j 的值的改变，也没有任何循环）
    
        i=j+1
    }
}

[dem0ns]

#19 回答作废

[dem0ns]

@msg7086 #17 是等价的吧

[msg7086]

@dem0ns a 全为 0 的时候，楼主的代码 O(N)，你的代码 O(N^2)。

[msg7086]

@dem0ns for i in range() 语法里的 i 是本地变量； for(;;)里的 i 是全局变量。

[dem0ns]

@msg7086 确实。打扰了。溜了溜了。

[dem0ns]

（再把锅甩给 github copilot 背，他转换的代码）

[msg7086]

从结果上来说，这代码确实是 O(N)，从算法角度来说解答得没错。
从代码本身来说，写得让人一眼看不出是 O(N)，就算面试官水平菜，但也能侧面反映出可读性不好。如果把 i 写成 left ，把 j 写成 right ，代码会清晰很多。

但是归根结底还是思路不清晰。
这题大概是让你找出所有的连续的 0 ，然后做一些操作吧。
那你的代码结构应该是这样的：

cursor = 0
while 还没找完 {
left = 找下个 0 段的左边界(cursor)
right = 找这个 0 段的右边界(left)
处理(left, right)
cursor = right+1
}

然后你再把每一步改写成真实的代码就行了。

如果我是这个面试官，我希望看到你首先写这 7 行框架，然后再分别把两个找边界的代码写在单独的函数 /方法里。而不是像楼主贴里那样随手开出两个 for 循环来瞎搞。

[msg7086]

另外，也可以把两个找边界的代码合并成一个，比如
left = find_next(0, cursor)
和
right = find_next(1, left) - 1
来实现找左右边界。

[hhjswf]

没上过高中吗，logn 复杂度比 n 小的多啊？

[wwbfred]

那个，logn 不比 n 更好么？你是不是想说 nlogn……

[eaststarpen]

> 你这两层遍历再怎么也不会是 O(n)，

这就暴露水平了

一层循环不一定是 O(n), 有可能是 log n 或 常数级

最简单的例子, 输出 [0, n] 2 的所有正整数倍数 就是 log_2 n `for(int x = 0; x <= n; x += 2) ...`

二层循环复杂度为 O(n) 的最常见例子是 线性筛(欧拉筛, 欧氏筛)

[eaststarpen]

@eaststarpen gcd 欧几里得算法 的循环实现是常数级(反阿克曼函数级),

[wwbfred]

简单看了下，找出数组中的全零子串，并从子串的第二个 0 开始做某些处理，我很好奇题目是让你干啥。
所以更易读的方法应该是设一个变量标记是否为第一个 0 ，然后用一个 for 循环。如果时间复杂度与空间复杂度相同，那么更容易理解的写法肯定是更好的。

[RollingTruck]

j 继承 i 的值并继续++, 最后再将值赋回给 i , 所以这里的 j , 作用其实等价于 i , 也就是 array 的遍历指针,
个人认为, 更好的写法是, 将原来的 i 记录为 i0, 然后对 i 进行自增操作

[lixiang2017]

1. 如何在提问时避免「 XY 问题」，请把原题目发出来。是不是找出所有零串？双指针写法，挺好的。
2. 时间复杂度是 O(N)。面试官水平不行，没去是好事。
3. 楼上用 chatgpt 的，不可信。chatgpt 写稿子可以，数学真不行。力扣周赛第四题，他基本做不出来。逻辑复杂的第一题，他也不行。
4. 利益相关。力扣刷了一千多了，这点认知还是有的。
5. 可以去私聊力扣或 B 站 灵神 帮你解惑。id: 灵茶山艾府

[Helsing]

没看懂你到底要干啥

话说写这样的代码不是找骂吗，一点都不好看懂

[sixseven111]

@dem0ns #9
内层循环结束会给 i 赋值啊，如果全 0 外层 1 次，内存 n-1 次直接结束了好吧

[ivvei]

复杂度上确实是 O(N), 但是你这 for 用得……

[urnoob]

我也在写过类似的发在国外版 leetcode 的互动区，被一个老外嘲讽。没理他。后来偶然发现 ta 自己删除了评论

[jmc891205]

确实是 O(n)
也确实有更清楚的写法