一个面试题，大家评评理

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

[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 的流程的，这个是面试人员马虎问题，