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

How to solve this without extra memory
Автор Bobek, история, 9 лет назад, По-английски

I am trying to solve this problem http://www.geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/ There is a solution, but in my opinion it's actually O(n^2) , because rotate function also is O(n). Am I right ? Is there a way to solve it in O(n) time and O(1) space ?

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

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

Yes, the approach with O(1) extra space runs in quadratic time.

As far as I know, it's only possible to do this with O(1) extra space in a linked list, not in an array. In an array, the best I know with linear time and constant space is preserving the order of one of the sides: positive xor negative, not both.

→ Ответить