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

2021年3月30日12:38:03 发表评论 527 次浏览

本文概述

``````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 ..``````

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 ;

// 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 ;

// 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 - = 1

if (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

# 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#

``````// 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 ;

// 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 ;

// 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
?>``````

``````Given array is
2 3 -4 -1 6 -9
Rearranged array is
-1 3 -4 2 -9 6``````