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

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

本文概述

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

例子：

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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: