重新排列数组，交替出现&个正数的负数项，多余的空间为O(1) | 系列 1 · GeeksForGeeks 中文系列教程

# 重新排列数组，交替出现&个正数的负数项，多余的空间为`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; } ```