c**i
发帖数: 306 | 1 Given an array of positive and negative integers, re-arrange it so that you
have positive integers on one end and negative integers on other, but retain
their order of appearance in the original array.
For example, given [1, 7, -5, 9, -12, 15]
The answer would be: [-5, -12, 1, 7, 9, 15]
This should be done in O(n) time and O(1) space. | h*********2
发帖数: 444 | | h***k
发帖数: 161 | 3 扫第一遍记录有多少个负数，作为正数starting index，扫第二遍two pointers不就完
了？ | h***k
发帖数: 161 | | c***r
发帖数: 280 | 5 要求in-place吗？ 如果不能再建一个array,想不出O(n)时间，O(1)空间的解法啊。
you
retain
【在 c**i 的大作中提到】
: Given an array of positive and negative integers, re-arrange it so that you
: have positive integers on one end and negative integers on other, but retain
: their order of appearance in the original array.
: For example, given [1, 7, -5, 9, -12, 15]
: The answer would be: [-5, -12, 1, 7, 9, 15]
: This should be done in O(n) time and O(1) space.
| c*****m
发帖数: 271 | 6 难道不就是quicksort里面的partition么？求拍 | r****7
发帖数: 2282 | 7 顺序会改变
【在 c*****m 的大作中提到】
: 难道不就是quicksort里面的partition么？求拍
| p****6
发帖数: 3 | 8 my answer of C++ version. This question actually is a partial of the
quicksort method.
void reorder(vector& nums)
{
int len = nums.size();
int start = -1;
for(int i = 0; i < len; i++)
{
if(nums[i] < 0)
swap(nums[i], nums[++start]);
}
} |
|
