算法（重新排列数组使正负项交替出现，使用O(1)空间|S2） _数组

本文概述

C ++
Java
Python3
C#
的PHP

给定正负数数组, 以其他方式排列它们, 使每个正数后跟负数, 反之亦然。输出中元素的顺序无关紧要。多余的正数或负数元素应移至末尾。
例子：

Input : arr[] = {-2, 3, 4, -1} Output : arr[] = {-2, 3, -1, 4} OR {-1, 3, -2, 4} OR ..Input : arr[] = {-2, 3, 1} Output : arr[] = {-2, 3, 1} OR {-2, 1, 3} Input : arr[] = {-5, 3, 4, 5, -6, -2, 8, 9, -1, -4} Output : arr[] = {-5, 3, -2, 5, -6, 4, -4, 9, -1, 8} OR ..

方法1：
首先，按非递增顺序对数组进行排序。然后我们将计算正整数和负整数的数目。
【算法（重新排列数组使正负项交替出现，使用O(1)空间|S2）】然后在奇数的位置交换1个负数和1个正数直到我们达到我们的条件。
这将重新排列数组元素，因为我们正在对数组进行排序，并根据需要从左到右访问元素。
以下是上述想法的实现。
C ++

// C++ program to rearrange // array in alternating // positive & negative items // with O(1) extra space #include < bits/stdc++.h> using namespace std; // Function to rearrange positive and negative // integers in alternate fashion. The below // solution doesn't maintain original order of // elements void rearrange( int arr[], int n) { int i = -1, j = n; // shift all negative values to the end while (i < j) { while (i < = n - 1 and arr[i] > 0) i += 1; while (j > = 0 and arr[j] < 0) j -= 1; if (i < j) swap(arr[i], arr[j]); } // i has index of leftmost // negative element if (i == 0 || i == n) return ; // start with first positive // element at index 0 // Rearrange array in alternating // positive & // negative items int k = 0; while (k < n & & i < n) { // swap next positive // element at even position // from next negative element. swap(arr[k], arr[i]); i = i + 1; k = k + 2; } } // Utility function to print an array void printArray( int arr[], int n) { for ( int i = 0; i < n; i++) cout < < arr[i] < < " " ; cout < < endl; } // Driver code int main() { int arr[] = {2, 3, -4, -1, 6, -9}; 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; }

Java

// Java program to rearrange // array in alternating // positive & negative // items with O(1) extra space class GFG { // Function to rearrange positive and negative // integers in alternate fashion. The below // solution doesn't maintain original order of // elements static void rearrange( int arr[], int n) { int i = 0 , j = n - 1 ; // shift all negative values to the end while (i < j) { while (i < = n - 1 & & arr[i] > 0 ) i += 1 ; while (j > = 0 & & arr[j] < 0 ) j -= 1 ; if (i < j) swap(arr, i, j); } // i has index of leftmost negative element if (i == 0 || i == n) return ; // start with first positive // element at index 0 // Rearrange array in alternating positive & // negative items int k = 0 ; while (k < n & & i < n) { // swap next positive element // at even position // from next negative element. swap(arr, k, i); i = i + 1 ; k = k + 2 ; } } // Utility function to print an array static void printArray( int arr[], int n) { for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); System.out.println( "" ); } static void swap( int arr[], int index1, int index2) { int c = arr[index1]; arr[index1]=arr[index2]; arr[index2]=c; } // Driver code public static void main(String[] args) { int arr[] = { 2 , 3 , - 4 , - 1 , 6 , - 9 }; int n = arr.length; System.out.println( "Given array is " ); printArray(arr, n); rearrange(arr, n); System.out.println( "Rearranged array is " ); printArray(arr, n); } } // This code is contributed by 29AjayKumar

Python3

# Python3 program to rearrange array # in alternating positive & negative # items with O(1) extra space # Function to rearrange positive and # negative integers in alternate fashion. # The below solution does not maintain # original order of elements def rearrange(arr, n): i = 0 j = n - 1 # shift all negative values # to the end while (i < j):while (i < = n - 1 and arr[i] > 0 ): i + = 1 while (j > = 0 and arr[j] < 0 ): j - = 1if (i < j): temp = arr[i] arr[i] = arr[j] arr[j] = temp# i has index of leftmost # negative element if (i = = 0 or i = = n): return 0 # start with first positive element # at index 0 # Rearrange array in alternating # positive & negative items k = 0 while (k < n and i < n):# swap next positive element at even # position from next negative element. temp = arr[k] arr[k] = arr[i] arr[i] = temp i = i + 1 k = k + 2 # Utility function to print an array def printArray(arr, n): for i in range (n): print (arr[i], end = " " ) print ( "\n" ) # Driver code arr = [ 2 , 3 ] n = len (arr) print ( "Given array is" ) printArray(arr, n) rearrange(arr, n) print ( "Rearranged array is" ) printArray(arr, n) # This code is contributed # Princi Singh

// C# program to rearrange array // in alternating positive & negative // items with O(1) extra space using System; class GFG { // Function to rearrange positive and // negative integers in alternate fashion. // The below solution doesn't maintain // original order of elements static void rearrange( int []arr, int n) { int i = 0, j = n - 1; // shift all negative values // to the end while (i < j) { while (i < = n - 1 & & arr[i] > 0) i += 1; while (j > = 0 & & arr[j] < 0) j -= 1; if (i < j) swap(arr, i, j); } // i has index of leftmost // negative element if (i == 0 || i == n) return ; // start with first positive // element at index 0 // Rearrange array in alternating // positive & negative items int k = 0; while (k < n & & i < n) { // swap next positive element // at even position from next // negative element. swap(arr, k, i); i = i + 1; k = k + 2; } } // Utility function to print an array static void printArray( int []arr, int n) { for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); Console.WriteLine( "" ); } static void swap( int []arr, int index1, int index2) { int c = arr[index1]; arr[index1] = arr[index2]; arr[index2] = c; } // Driver code public static void Main() { int []arr = {2, 3, -4, -1, 6, -9}; int n = arr.Length; Console.WriteLine( "Given array is " ); printArray(arr, n); rearrange(arr, n); Console.WriteLine( "Rearranged array is " ); printArray(arr, n); } } // This code is contributed // by 29AjayKumar

的PHP

< ?php // PHP program to rearrange array // in alternating positive & negative // items with O(1) extra space // Function to rearrange positive and // negative integers in alternate fashion. // The below solution doesn't maintain // original order of elements function rearrange(& $arr , $n ) { $i = 0; $j = $n - 1; // shift all negative values // to the end while ( $i < $j ) {while ( $i < = $n - 1 and $arr [ $i ] > 0) ++ $i ; while ( $j > = 0 and $arr [ $j ] < 0) -- $j ; if ( $i < $j ) { $temp = $arr [ $i ]; $arr [ $i ] = $arr [ $j ]; $arr [ $j ] = $temp ; } } // i has index of leftmost // negative element if ( $i == 0 || $i == $n ) return ; // start with first positive element // at index 0 // Rearrange array in alternating // positive & negative items $k = 0; while ( $k < $n & & $i < $n ) { // swap next positive element at even // position from next negative element. $temp = $arr [ $k ]; $arr [ $k ] = $arr [ $i ]; $arr [ $i ] = $temp ; $i = $i + 1; $k = $k + 2; } } // Utility function to print an array function printArray(& $arr , $n ) { for ( $i = 0; $i < $n ; $i ++) echo $arr [ $i ] . " " ; echo "\n" ; } // Driver code $arr = array (2, 3, -4, -1, 6, -9); $n = sizeof( $arr ); echo "Given array is \n" ; printArray( $arr , $n ); rearrange( $arr , $n ); echo "Rearranged array is \n" ; printArray( $arr , $n ); // This code is contributed // by ChitraNayal ?>

输出如下：