水题TLE求助

花里心爱 @ 2018-09-15 17:03:43

by 花里心爱 @ 2018-09-15 18:18:18

@AC我最萌 不会手写，我菜的很

by Rbu_nas @ 2018-09-15 18:20:31

@Irressey 就弄个list数组嘛qwq

by Rbu_nas @ 2018-09-15 18:24:55

@Irressey queue一出队就是一个O(n)玩不起啊

by 花里心爱 @ 2018-09-15 18:26:30

@AC我最萌 STL的queue出队操作是O(n)的？qwq惊了

by Rbu_nas @ 2018-09-15 18:28:34

@Irressey

假设队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并将n个元素存储在数组的前n个单元中，数组下标为0的一端为队头。

所谓的插入队列操作，其实是在队尾追加一个元素，不需要移动任何元素，时间复杂度为 O(1) 。

和栈不同，队列的出列操作在队头进行，即下标为0的位置，即队列中的所有元素都要向前移动，保证队列的队头在下标为0的位置且不为空，此时的时间复杂度为 O(n)

by 花里心爱 @ 2018-09-15 18:30:20

@AC我最萌 谢谢了qwq

by 花里心爱 @ 2018-09-15 18:31:57

@AC我最萌 然而RE了qwq

by Rbu_nas @ 2018-09-15 18:33:10

@Irressey 好...好桑心QAQ

by Rbu_nas @ 2018-09-15 18:33:28

@Irressey 我太笨了，看来帮不到您了

by Rbu_nas @ 2018-09-15 18:34:28

@夜刀神十香ღ @Miku初音 @Kirito_Rivaille