Учитывая массив положительных и отрицательных целых чисел, переставьте его так, чтобы у вас были положительные целые числа на одном конце и отрицательные целые числа на

Недавно я наткнулся на вопрос на собеседовании Microsoft для инженера-программиста.

Учитывая массив положительных и отрицательных целых чисел, переставьте его так, чтобы у вас были положительные целые числа на одном конце и отрицательные целые числа на другом, , но сохранил их порядок появления в исходном массиве.

Например, , учитывая [1, 7, -5, 9, -12, 15]
Ответ будет: [- 5, -12, 1, 7, 9, 15]

Это должно быть сделано за O (n).

Мы могли бы легко сделать это за O (n), но я не могу представить, как мы можем поддерживать порядок элементов, как в исходном массиве. Если мы забудем о сложности O (n), не мог бы кто-нибудь сказать мне, как мы можем сохранить порядок элементов, не принимая во внимание пространственную и временную сложность.

EDIT : На самом деле мы должны иметь O ( 1) также космическая сложность.