本文概述
给定正负数数组, 以其他方式排列它们, 使每个正数后跟负数, 反之亦然。输出中元素的顺序无关紧要。多余的正数或负数元素应移至末尾。
例子:
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:
首先,按非递增顺序对数组进行排序。然后我们将计算正整数和负整数的数目。
然后在奇数的位置交换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 - = 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
# 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#
// 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
?>
输出如下:
Given array is
2 3 -4 -1 6 -9
Rearranged array is
-1 3 -4 2 -9 6
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。