# 重新排列數組，交替出現&個正數的負數項，多余的空間為`O(1)` | 系列 1 > 原文： [https://www.geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/](https://www.geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/) 給定正負數組，以其他方式排列它們，使每個正數后跟負數，反之亦然，以保持外觀順序。 正數和負數不必相等。 如果有更多正數，它們將出現在數組的末尾。 如果還有更多負數，它們也會出現在數組的末尾。 **示例**： ``` 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} ``` 這個問題在很多地方都被問過（請參閱[這個](https://www.geeksforgeeks.org/amazon-interview-set-118-campus-internship/)和[這個](https://www.geeksforgeeks.org/amazon-interview-set-114-campus-internship/)） 如果允許`O(n)`多余的空間，則可以輕松解決上述問題。 由于`O(1)`的額外空間和出現順序的限制，它變得很有趣。 這個想法是從左到右處理數組。 在處理時，在剩余的未處理數組中找到第一個不合適的元素。 如果元素為負且索引為奇數，或者為正且索引為偶數，則該元素不合適。 一旦找到不適當的元素，我們將在它后面找到帶有相反符號的第一個元素。 我們在這兩個元素（包括這兩個）之間右旋轉子數組。 以下是上述想法的實現。 ## C++ ```cpp /*? C++ program to rearrange positive and negative integers in alternate ????fashion while keeping the order of positive and negative numbers. */ #include <iostream> #include <assert.h> using namespace std; // Utility function to right rotate all elements between [outofplace, cur] 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) ????????{ ????????????// find the item which must be moved into the out-of-place ????????????// entry if out-of-place entry is positive and current ????????????// entry is negative OR if out-of-place entry is negative ????????????// and current entry is negative then right rotate ????????????// ????????????// [...-3, -4, -5, 6...] -->?? [...6, -3, -4, -5...] ????????????//????? ^????????????????????????? ^ ????????????//????? |????????????????????????? | ????????????//???? outofplace????? -->????? outofplace ????????????// ????????????if (((arr[index] >= 0) && (arr[outofplace] < 0)) ????????????????|| ((arr[index] < 0) && (arr[outofplace] >= 0))) ????????????{ ????????????????rightrotate(arr, n, outofplace, index); ????????????????// the new out-of-place entry is now 2 steps ahead ????????????????if (index - outofplace >= 2) ????????????????????outofplace = outofplace + 2; ????????????????else ????????????????????outofplace = -1; ????????????} ????????} ????????// if no entry has been flagged out-of-place ????????if (outofplace == -1) ????????{ ????????????// check if current entry is out-of-place ????????????if (((arr[index] >= 0) && (!(index & 0x01))) ????????????????|| ((arr[index] < 0) && (index & 0x01))) ????????????{ ????????????????outofplace = index; ????????????} ????????} ????} } // A utility function to print an array 'arr[]' of size 'n' void printArray(int arr[], int n) { ????for (int i = 0; i < n; i++) ??????cout << arr[i] << " "; ????cout << endl; } // Driver program to test abive function int main() { ????//int arr[n] = {-5, 3, 4, 5, -6, -2, 8, 9, -1, -4}; ????//int arr[] = {-5, -3, -4, -5, -6, 2 , 8, 9, 1 , 4}; ????//int arr[] = {5, 3, 4, 2, 1, -2 , -8, -9, -1 , -4}; ????//int arr[] = {-5, 3, -4, -7, -1, -2 , -8, -9, 1 , -4}; ????int arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}; ????int n = sizeof(arr)/sizeof(arr[0]); ????cout << "Given array is \n"; ????printArray(arr, n); ????rearrange(arr, n); ????cout << "Rearranged array is \n"; ????printArray(arr, n); ????return 0; } ```