一个面试题，大家评评理

[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
    }
}

就大家回复讨论中出现的几点问题统一回复下：
1 、关于面试官说的 logN 的问题。
我在发帖的时候心里也犯嘀咕，我都怀疑我是不是记错面试官的话了，回忆了半天感觉还是感觉自己记忆中他说的是 logN 而不是 NlogN 。但并不百分百排除是我记错了或者听错了。不过这个不作为重点吧，个人感觉无非五十步还是百步的问题，问题的性质没变。
2 、我的代码风格问题。
毫无疑问是不好的，硬要为自己找借口的话，可以说自己近 10 年没做过系统性工程性开发，所以没有良好的编码习惯，也可以说本身水平就很一般当时也比较仓促就写得不精细。总之，说我代码风格不好、可读性及细节可以优化、没实现题目目标啥的，我都认了，就是这个时间复杂度真的令我震惊。
3 、题目及去不去也罢的问题。
只能说对方是 tz 里可以算 top3 的地方，所以即使 v2 需要特殊技巧才能访问也不多说原题目是啥了，再说毕竟仅仅是讨论代码片段的性能而不是是否符合题目要求。
本身也只是去水一下，并没抱多大期待，毕竟就算面试过了后续也挺麻烦的。
只是感慨，只要坐在合适的位置，说什么话都是理直气壮的真理。人不仅跟宇宙比是渺小的，跟人群比也是渺小的，找对平台比学对技术更重要。

[reter]

个人感觉也是 O(n). 说明 面试官 根本没有仔细看你的逻辑，认为有两个循环就是 O(n^2)

[theguagua]

确实是 O(n)，对于数组 a 中的每个元素，只需进行常数时间的操作，没有嵌套循环。

[ulala]

「你这两层遍历再怎么也不会是 O(n)，最多算 O(logn)」这面试官是不是对这两个复杂度的大小有误解，还是你说错了

[akaxiaok339]

问 AI 说是 O(n)

[pipasese]

面试官不行，不去也罢

[hefish]

在乎别人是好事，太在乎容易进入怪圈。。面试官也就是比你多吃几年萝卜干饭，过几年说不定面试官也要失业，到时候说不定就是你面试他了。

[hello2090]

看半天没看懂，觉得面试官说的没错啊。算法复杂度肯定不是说在某一个特定输入下，你这个两层循环为啥不是 n^2?

[ibinary]

外层 for 循环遍历数组 a 一次,时间复杂度 O(n)
内层 for 循环找到下一个不为 0 的元素,时间复杂度 O(m),其中 m 为 0 的元素个数
由于 m<n,所以内层 for 循环的时间复杂度可以看作 O(1)
结合外层 for 循环,总时间复杂度为 O(n)*O(1)=O(n)

[dem0ns]

这得根据 a 的值来看吧，a 全为 0 的时候也不是 O(n)啊，对于#4 的 AI ，我试了，刚开始给的答案也是 O(n)，后来纠正为 n^2 的


```
我对之前的回答有误解，请接受我的道歉。如果数组 a 的值全部为 0 ，那么内层循环无法找到下一个非零元素的意思是，由于数组中所有元素都是 0 ，内层循环的条件 a[j] == 0 永远为真，内层循环会一直执行直到 j 超出数组范围。

在这种情况下，代码的时间复杂度为 O(n^2)，其中 n 是数组 a 的长度。

外层的 for 循环会遍历整个数组 a ，这需要执行 n 次循环。

内层的 while 循环会在每次遇到 a[i] == 0 的情况下执行，并且会一直向后搜索直到找到下一个非零元素或者到达数组末尾。由于数组中所有元素都是 0 ，内层循环会执行 n - i 次，其中 i 是外层循环的迭代变量。

因此，总的时间复杂度是 O(n * (n - i))，即 O(n^2)。
```

[dem0ns]

https://www.baidu.com/s?wd=时间复杂度是按照是坏情况吗

[C47CH]

明显是 O(N)，O(logN)咋想的，怕不是有什么误解。

[xenme]

@dem0ns 你看最后还有一个 i=j+1

[ViriF]

O(logN)还有这种好事？也没排过序啊......

[dem0ns]

@xenme 我知道，但是复现后不符合 O(n)

if __name__ == '__main__':
count = 0
a = [0, 0, 0, 0, 0, 0, 0, 0]
print(len(a))
for i in range(len(a)):
if a[i] == 0:
j = i + 1
while j < len(a) and a[j] == 0:
count += 1 # 计数
j += 1 # j++
print(count, end=" ")
i = j + 1


把数组 a 依次添 0 ，得到的 count 为 3 ，6 ，10 ，15 ，21.....

O(n)应该是均匀递增才对？ （这里需要指教下）

[dem0ns]

对于#9 的补充，我不认同 O(n^2)，但也对 O(n)持怀疑

[grance]

O(nlogn)

[msg7086]

@dem0ns #14
for i in range(len(a))
与原题
for (i=0;i<a.length;i++)
不等价。

[GeruzoniAnsasu]

没去成是好事


还 logn ，与 n 比哪个更快都搞不清；就算他说的是 nlogn ，算法里的 log 都是以 2 为底的，logN 这个多项式代表「能在 N 次二分内找到目标」，其必定会对应某种分治思路。这算法里根本就没有分治，无论如何都凑不出 log

[dem0ns]

@msg7086 #17
确实忘记加了，但在 a 全为 0 的时候不影响结果

[qzeng2017]

虽然没看题目是什么，但是看你写的这个循环代码就不行，不仅容易出错，看的人也吃力，这种算法题基本都可以用很优雅的循环或者别的方式解决

[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)
也确实有更清楚的写法

[buxudashi]

分成 2 段共同为 N ，一点不多不少。

[NeroKamin]

确实是 O(n)，但是是不是用双指针写法会更清晰一点？随口一说，没仔细看，可能说错了

[tyrantZhao]

不去是好事，这对面的面试官压根不懂

[vcbal]

@hello2090 你把内循环理解成 枚举判断这样就可以了哈，也就是每次循环 内循环只用走常数次 而不是 n 次

[sloknyyz]

内层还有个 i=j+1,所以即使是全 0 的情况下，也只会遍历一次，这就是 O(N)。

[izzy27]

没去成是好事，真的

[Badlink]

典型的双指针啊，面试官水平不好评价，没去也好

[arthuryangcs]

面试官水平不行

[ssw2]

是 O(n)，但你这写得确实难看

[C2Z]

虽然感觉写的确实很怪。。但是真的有这种水平的面试吗（纯好奇，刚转码，没有别的意思）

[n18255447846]

1<log(n)<n<n*n

[iosyyy]

@ibinary 只有在 m<<<n 的情况下才能视为 o(1)

[iosyyy]

@ibinary 这段代码确实在 o(n)但是你这个解释完全不对

[mmdsun]

看到这里你就应该跑了 面试官：你这两层遍历再怎么也不会是 O(n)，最多算 O(logn)

logn 不比 n 要快？？

[WashFreshFresh]

确实 logn 比快呀，进来一看差点把我搞懵了。

[WashFreshFresh]

@WashFreshFresh 打错 是 logn 比 n 快

[unco020511]

原谅我 你这个两个循环我差点没看明白

[zhandi4]

@n18255447846 还有一个 nlogn

[Huelse]

你这第二个循环确实容易误导人，但这面试官水平也有限，所以不必深究。

说不定其他几位面试官是知道的，但是不说，但内心也知道这个人的水平了😎

[dode]

i=j+1 显然内部循环可以优化外面循环 i 的流程的，这个是面试人员马虎问题，

[yuruizhe]

前后双指针，是 O(n)

[yuruizhe]

@lixiang2017 居然能看出题目原意是“找出所有的 0”，那感觉一个 for 就够了…

[lixiang2017]

@yuruizhe 嗯，一层循环就行，用个变量记录之前的下标，满足一定条件就去处理数据或更新下标。