第三题只用 bfs,复杂度是 n 平方。我的优化方法是用一个有序表,存储目前还没被访问过的所有下标,初始化时存起来所有下标。然后在 bfs 过程中,为了把当前下标左边所有未被访问的下标加入到队列,可以从头遍历一遍有序表直到比当前下标大。而且每加入一个下标到队列,就相应地从有序表中移除,所以均摊下来复杂度 nlogn
点赞 1

相关推荐

牛客网
牛客企业服务