Given an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and vice-versa maintaining the order of appearance.
Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.
Example:
Input: arr[] = {1, 2, 3, -4, -1, 4}
Output: arr[] = {-4, 1, -1, 2, 3, 4}
Input: arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
output: arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}
The above problem can be easily solved if O(n) extra space is allowed. It becomes interesting due to the limitations that O(1) extra space and order of appearances.
The idea is to process array from left to right. While processing, find the first out of place element in the remaining unprocessed array. An element is out of place if it is negative and at odd index, or it is positive and at even index. Once we find an out of place element, we find the first element after it with opposite sign. We right rotate the subarray between these two elements (including these two).
The above problem can be easily solved if O(n) extra space is allowed. It becomes interesting due to the limitations that O(1) extra space and order of appearances.
The idea is to process array from left to right. While processing, find the first out of place element in the remaining unprocessed array. An element is out of place if it is negative and at odd index, or it is positive and at even index. Once we find an out of place element, we find the first element after it with opposite sign. We right rotate the subarray between these two elements (including these two).
void rightrotate(int arr[], int n, int outofplace, int cur)
{
char tmp = arr[cur];
for (int i = cur; i > outofplace; i--)
arr[i] = arr[i-1];
arr[outofplace] = tmp;
}
void rearrange(int arr[], int n)
{
int outofplace = -1;
for (int index = 0; index < n; index ++)
{
if (outofplace >= 0)
{
if (((arr[index] >= 0) && (arr[outofplace] < 0))
|| ((arr[index] < 0) && (arr[outofplace] >= 0)))
{
rightrotate(arr, n, outofplace, index);
if (index - outofplace > 2)
outofplace = outofplace + 2;
else
outofplace = -1;
}
}
if (outofplace == -1)
{
if (((arr[index] >= 0) && (!(index & 0x01)))
|| ((arr[index] < 0) && (index & 0x01)))
{
outofplace = index;
}
}
}
}
Also check
http://tech-wonderland.net/blog/interview-questions-sort-negative-and-positive-numbers.html
方法三, O(NlogN)时间, O(logN)空间: 利用分治算法, 每次对数组的两边进行重新排序, 同时返回两个half部分的正负数分界点. 然后可以在线性时间内将left part中的正数部分和right part中的负数部分交换, 那么整体就符合要求了.
01 | int reorder3(std::vector<int> &nums, int p, int r) { |
12 | if(nums[r] < 0 && nums[p] > 0) { |
13 | std::swap(nums[p], nums[r]); |
16 | if(nums[r] > 0 && nums[p] < 0) { |
19 | if(nums[r] < 0 && nums[p] < 0) { |
25 | int q = p + (r - p) / 2; |
26 | int left = reorder3(nums, p, q - 1); |
27 | int right = reorder3(nums, q, r); |
29 | if(-1 == left) return right; |
31 | flip(nums, left, q, r); |
32 | return r + 1 - (q - left); |
34 | flip(nums, left, q, right - 1); |
35 | return right - (q - left); |
Read full article from
Rearrange array in alternating positive & negative items with O(1) extra space - GeeksforGeeks
