一个面试题，大家评评理

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 552 天前的主题，其中的信息可能已经有所发展或是发生改变。

这两天去水了个面试，瞎写了一段代码，姑且不论这段代码能不能实现目标，面试现场 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 条附言 · 2023-05-22 10:39:17 +08:00

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

遍历

面试

length

代码

63 条回复 • 2023-05-22 21:08:29 +08:00

reter

2023-05-19 18:41:13 +08:00

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

theguagua

2023-05-19 18:44:24 +08:00

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

ulala

2023-05-19 18:45:05 +08:00

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

akaxiaok339

2023-05-19 18:51:08 +08:00

问 AI 说是 O(n)

pipasese

2023-05-19 18:58:29 +08:00 via iPhone

面试官不行，不去也罢

hefish

2023-05-19 19:01:05 +08:00

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

hello2090

2023-05-19 19:03:50 +08:00

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

ibinary

2023-05-19 19:07:17 +08:00

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

dem0ns

2023-05-19 19:10:18 +08:00

这得根据 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

2023-05-19 19:11:43 +08:00

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

C47CH

2023-05-19 19:13:35 +08:00

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

xenme

2023-05-19 19:14:13 +08:00 via iPhone

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

ViriF

2023-05-19 19:20:08 +08:00

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

dem0ns

2023-05-19 19:20:55 +08:00

@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

2023-05-19 19:23:45 +08:00

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

grance

2023-05-19 19:24:57 +08:00

O(nlogn)

msg7086

2023-05-19 19:34:12 +08:00

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

GeruzoniAnsasu

2023-05-19 19:35:06 +08:00

没去成是好事

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

dem0ns

2023-05-19 19:37:17 +08:00

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

qzeng2017

2023-05-19 19:37:59 +08:00

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

dem0ns

2023-05-19 19:38:02 +08:00

#19 回答作废

dem0ns

2023-05-19 19:39:22 +08:00

@msg7086 #17 是等价的吧

msg7086

2023-05-19 19:41:26 +08:00

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

msg7086

2023-05-19 19:43:32 +08:00

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

dem0ns

2023-05-19 19:45:32 +08:00

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

dem0ns

2023-05-19 19:46:31 +08:00

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

msg7086

2023-05-19 19:55:43 +08:00

从结果上来说，这代码确实是 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

2023-05-19 19:57:56 +08:00

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

hhjswf

2023-05-19 19:59:54 +08:00

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

wwbfred

2023-05-19 20:04:51 +08:00

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

eaststarpen

2023-05-19 20:12:50 +08:00

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

这就暴露水平了

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

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

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

eaststarpen

2023-05-19 20:14:43 +08:00

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

wwbfred

2023-05-19 20:21:11 +08:00

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

RollingTruck

2023-05-19 20:31:21 +08:00

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

lixiang2017

2023-05-19 20:40:44 +08:00 via Android

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