Учитывая массив положительных и отрицательных чисел, расположите их альтернативным способом так, чтобы за каждым положительным числом следовал отрицательный, и наоборот, поддерживая порядок появления.
Количество положительных и отрицательных чисел не должно быть одинаковым. Если есть больше положительных чисел, они появляются в конце массива. Если есть больше отрицательных чисел, они тоже появляются в конце массива.
Примеры :
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}
Этот вопрос задавался во многих местах (см. Это и это )
Вышеупомянутая проблема может быть легко решена, если O (n) лишний пробел позволен. Это становится интересным из-за того, что O (1) лишнее пространство и порядок появления.
Идея состоит в том, чтобы обрабатывать массив слева направо. Во время обработки найдите первый неуместный элемент в оставшемся необработанном массиве. Элемент неуместен, если он отрицательный и имеет нечетный индекс, или он является положительным и имеет четный индекс. Как только мы находим неуместный элемент, мы находим первый элемент после него с противоположным знаком. Вращаем правую подрешетку между этими двумя элементами (включая эти два).
Ниже приводится реализация вышеуказанной идеи.
C ++
#include <iostream> #include <assert.h>
using namespace std;
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)
{
if (((arr[index] >= 0) && (arr[outofplace] < 0))
|| ((arr[index] < 0) && (arr[outofplace] >= 0)))
{
rightrotate(arr, n, outofplace, index);
if (index - outofplace >= 2)
outofplace = outofplace + 2;
else
outofplace = -1;
}
}
if (outofplace == -1)
{
if (((arr[index] >= 0) && (!(index & 0x01)))
|| ((arr[index] < 0) && (index & 0x01)))
{
outofplace = index;
}
}
}
}
void printArray( int arr[], int n)
{
for ( int i = 0; i < n; i++)
cout << arr[i] << " " ;
cout << endl;
}
int main()
{
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;
}
|
Джава
class RearrangeArray
{
void rightrotate( int arr[], int n, int outofplace, int cur)
{
int 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 )
{
if (((arr[index] >= 0 ) && (arr[outofplace] < 0 ))
|| ((arr[index] < 0 ) && (arr[outofplace] >= 0 )))
{
rightrotate(arr, n, outofplace, index);
if (index - outofplace > 2 )
outofplace = outofplace + 2 ;
else
outofplace = - 1 ;
}
}
if (outofplace == - 1 )
{
if (((arr[index] >= 0 ) && ((index & 0x01 )== 0 ))
|| ((arr[index] < 0 ) && (index & 0x01 )== 1 ))
outofplace = index;
}
}
}
void printArray( int arr[], int n)
{
for ( int i = 0 ; i < n; i++)
System.out.print(arr[i] + " " );
System.out.println( "" );
}
public static void main(String[] args)
{
RearrangeArray rearrange = new RearrangeArray();
int arr[] = {- 5 , - 2 , 5 , 2 , 4 , 7 , 1 , 8 , 0 , - 8 };
int n = arr.length;
System.out.println( "Given array is " );
rearrange.printArray(arr, n);
rearrange.rearrange(arr, n);
System.out.println( "RearrangeD array is " );
rearrange.printArray(arr, n);
}
}
|
python3
def rightRotate(arr, n, outOfPlace, cur):
temp = arr[cur]
for i in range (cur, outOfPlace, - 1 ):
arr[i] = arr[i - 1 ]
arr[outOfPlace] = temp
return arr
def rearrange(arr, n):
outOfPlace = - 1
for index in range (n):
if (outOfPlace > = 0 ):
if ((arr[index] > = 0 and arr[outOfPlace] < 0 ) or
(arr[index] < 0 and arr[outOfPlace] > = 0 )):
arr = rightRotate(arr, n, outOfPlace, index)
if (index - outOfPlace > 2 ):
outOfPlace + = 2
else :
outOfPlace = - 1
if (outOfPlace = = - 1 ):
if ((arr[index] > = 0 and index % 2 = = 0 ) or
(arr[index] < 0 and index % 2 = = 1 )):
outOfPlace = index
return arr
arr = [ - 5 , - 2 , 5 , 2 , 4 ,
7 , 1 , 8 , 0 , - 8 ]
print ( "Given Array is:" )
print (arr)
print ( "\nRearranged array is:" )
print (rearrange(arr, len (arr)))
|
C #
using System;
class GFG
{
static void rightrotate( int []arr, int n,
int outofplace, int cur)
{
int tmp = arr[cur];
for ( int i = cur; i > outofplace; i--)
arr[i] = arr[i - 1];
arr[outofplace] = tmp;
}
static void rearrange( int []arr, int n)
{
int outofplace = -1;
for ( int index = 0; index < n; index++)
{
if (outofplace >= 0)
{
if (((arr[index] >= 0) &&
(arr[outofplace] < 0)) ||
((arr[index] < 0) &&
(arr[outofplace] >= 0)))
{
rightrotate(arr, n, outofplace, index);
if (index - outofplace > 2)
outofplace = outofplace + 2;
else
outofplace = -1;
}
}
if (outofplace == -1)
{
if (((arr[index] >= 0) &&
((index & 0x01)==0)) ||
((arr[index] < 0) &&
(index & 0x01)==1))
outofplace = index;
}
}
}
static void printArray( int []arr, int n)
{
for ( int i = 0; i < n; i++)
Console.Write(arr[i] + " " );
Console.WriteLine( "" );
}
public static void Main()
{
int []arr = {-5, -2, 5, 2, 4,
7, 1, 8, 0, -8};
int n = arr.Length;
Console.WriteLine( "Given array is " );
printArray(arr, n);
rearrange(arr, n);
Console.WriteLine( "RearrangeD array is " );
printArray(arr, n);
}
}
|
PHP
<?php
function rightrotate(& $arr , $n ,
$outofplace , $cur )
{
$tmp = $arr [ $cur ];
for ( $i = $cur ; $i > $outofplace ; $i --)
$arr [ $i ] = $arr [ $i - 1];
$arr [ $outofplace ] = $tmp ;
}
function rearrange(& $arr , $n )
{
$outofplace = -1;
for ( $index = 0; $index < $n ; $index ++)
{
if ( $outofplace >= 0)
{
if ((( $arr [ $index ] >= 0) && ( $arr [ $outofplace ] < 0)) ||
(( $arr [ $index ] < 0) && ( $arr [ $outofplace ] >= 0)))
{
rightrotate( $arr , $n , $outofplace , $index );
if ( $index - $outofplace > 2)
$outofplace = $outofplace + 2;
else
$outofplace = -1;
}
}
if ( $outofplace == -1)
{
if ((( $arr [ $index ] >= 0) && (!( $index & 0x01)))
|| (( $arr [ $index ] < 0) && ( $index & 0x01)))
{
$outofplace = $index ;
}
}
}
}
function printArray(& $arr , $n )
{
for ( $i = 0; $i < $n ; $i ++)
echo $arr [ $i ]. " " ;
echo "\n" ;
}
$arr = array (-5, -2, 5, 2, 4, 7, 1, 8, 0, -8);
$n = sizeof( $arr );
echo "Given array is \n" ;
printArray( $arr , $n );
rearrange( $arr , $n );
echo "Rearranged array is \n" ;
printArray( $arr , $n );
?>
|
Выход:
Given array is
-5 -2 5 2 4 7 1 8 0 -8
Rearranged array is
-5 5 -2 2 -8 4 7 1 8 0
Перестановка массива в чередующихся положительных и отрицательных элементах с O (1) дополнительным пробелом | Набор 2
Эта статья предоставлена Сандипом Джоши . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
- Перестановка массива в чередующихся положительных и отрицательных элементах с O (1) дополнительным пробелом | Набор 2
- Переставьте положительные и отрицательные числа в O (n) время и O (1) дополнительное пространство
- Переставьте положительные и отрицательные числа с постоянным лишним пробелом
- Переместите все отрицательные числа в начало и положительные в конец с постоянным лишним пробелом
- Переставьте массив так, чтобы arr [i] стал arr [arr [i]] с O (1) дополнительным пробелом
- Переставить массив в максимально минимальной форме | Набор 2 (O (1) дополнительное пространство)
- Проверьте, являются ли элементы массива последовательными во времени O (n) и пространстве O (1) (обрабатывает как положительные, так и отрицательные числа)
- Самый длинный чередующийся (положительный и отрицательный) подмассив, начинающийся с каждого индекса
- Переставьте положительные и отрицательные числа с помощью встроенной функции сортировки
- Лямбда-выражение в Python для перестановки положительных и отрицательных чисел
- Переместите все отрицательные элементы в конец в порядке с дополнительным пробелом
- Разделение отрицательного и положительного поддержания порядка и пространства O (1)
- Только целое с положительным значением в положительном отрицательном значении в массиве
- Пары положительных отрицательных значений в массиве
- Перемешать массив {a1, a2, .. an, b1, b2, .. bn} как {a1, b1, a2, b2, a3, b3, ……, an, bn} без использования дополнительного пространства
Перестановка массива в чередующихся положительных и отрицательных элементах с O (1) дополнительным пробелом | Комплект 1
0.00 (0%) 0 votes