Блог пользователя wiaderko69

Автор wiaderko69, история, 16 месяцев назад, По-английски

Can someone tell me what's the time complexity of this code? I thought it's O(N^2) because of vector erase but it gets AC 332397335.

Code
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
16 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by wiaderko69 (previous revision, new revision, compare).

»
16 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

It's O(N)

»
16 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Your code is indeed $$$\mathcal{O}(n^2)$$$ consider a case where $$$c = 2$$$ and $$$a$$$ consists of $$$x$$$ ones, next $$$x+1$$$ twos and finally $$$1$$$ one; $$$n$$$ would be equal to $$$2x+2$$$.