Dada una array de números positivos y negativos, organícelos de manera alterna de modo que cada número positivo sea seguido por uno negativo y viceversa, manteniendo el orden de aparición.
El número de números positivos y negativos no tiene por qué ser igual. Si hay más números positivos, aparecen al final de la array. Si hay más números negativos, también aparecen al final de la array.
Ejemplos:
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}
Esta pregunta se ha hecho en muchos lugares (Ver esto y esto )
Enfoque ingenuo :
El problema anterior se puede resolver fácilmente si se permite O(n) espacio extra. Se vuelve interesante debido a las limitaciones que tiene O(1) extra de espacio y orden de aparición.
La idea es procesar la array de izquierda a derecha. Mientras procesa, busque el primer elemento fuera de lugar en la array restante sin procesar. Un elemento está fuera de lugar si es negativo y tiene un índice impar (índice basado en 0), o si es positivo y tiene un índice par (índice basado en 0). Una vez que encontramos un elemento fuera de lugar, encontramos el primer elemento después de él con signo opuesto. Giramos a la derecha el subarreglo entre estos dos elementos (incluidos estos dos).
A continuación se muestra la implementación de la idea anterior.
C++
/* C++ program to rearrange
positive and negative integers
in alternate fashion while keeping
the order of positive and negative numbers. */
#include <assert.h>
#include <iostream>
using namespace std;
// Utility function to right rotate all elements between
// [outofplace, cur]
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)
{
// find the item which must be moved into the
// out-of-place entry if out-of-place entry is
// positive and current entry is negative OR if
// out-of-place entry is negative and current
// entry is negative then right rotate
//
// [...-3, -4, -5, 6...] --> [...6, -3, -4,
// -5...]
// ^ ^
// | |
// outofplace --> outofplace
//
if (((arr[index] >= 0) && (arr[outofplace] < 0))
|| ((arr[index] < 0)
&& (arr[outofplace] >= 0)))
{
rightrotate(arr, n, outofplace, index);
// the new out-of-place entry is now 2 steps
// ahead
if (index - outofplace >= 2)
outofplace = outofplace + 2;
else
outofplace = -1;
}
}
// if no entry has been flagged out-of-place
if (outofplace == -1) {
// check if current entry is out-of-place
if (((arr[index] >= 0) && (!(index & 0x01)))
|| ((arr[index] < 0) && (index & 0x01))) {
outofplace = index;
}
}
}
}
// A utility function to print an array 'arr[]' of size 'n'
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver code
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;
}
Java
class RearrangeArray
{
// Utility function to right rotate all elements
// between [outofplace, cur]
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)
{
// find the item which must be moved into
// the out-of-place entry if out-of-place
// entry is positive and current entry is
// negative OR if out-of-place entry is
// negative and current entry is negative
// then right rotate
//
// [...-3, -4, -5, 6...] --> [...6, -3,
// -4, -5...]
// ^ ^
// | |
// outofplace --> outofplace
//
if (((arr[index] >= 0)
&& (arr[outofplace] < 0))
|| ((arr[index] < 0)
&& (arr[outofplace] >= 0))) {
rightrotate(arr, n, outofplace, index);
// the new out-of-place entry is now 2
// steps ahead
if (index - outofplace >= 2)
outofplace = outofplace + 2;
else
outofplace = -1;
}
}
// if no entry has been flagged out-of-place
if (outofplace == -1)
{
// check if current entry is out-of-place
if (((arr[index] >= 0)
&& ((index & 0x01) == 0))
|| ((arr[index] < 0)
&& (index & 0x01) == 1))
outofplace = index;
}
}
}
// A utility function to print
// an array 'arr[]' of size 'n'
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println("");
}
// Driver Code
public static void main(String[] args)
{
RearrangeArray rearrange = new RearrangeArray();
/* int arr[n] = {-5, 3, 4, 5, -6,
-2, 8, 9, -1, -4};
int arr[] = {-5, -3, -4, -5, -6,
2 , 8, 9, 1 , 4};
int arr[] = {5, 3, 4, 2, 1,
-2 , -8, -9, -1 , -4};
int arr[] = {-5, 3, -4, -7,
-1, -2 , -8, -9, 1 , -4};*/
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);
}
}
// This code has been contributed by Mayank Jaiswal
Python
# Python3 program to rearrange
# positive and negative integers
# in alternate fashion and
# maintaining the order of positive
# and negative numbers
# rotates the array to right by once
# from index 'outOfPlace to cur'
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 element at outOfPlace place in
# negative and if element at index
# is positive we can rotate the
# array to right or if element
# at outOfPlace place in positive and
# if element at index is negative we
# can rotate the array to right
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):
# conditions for A[index] to
# be in out of place
if((arr[index] >= 0 and index % 2 == 0) or
(arr[index] < 0 and index % 2 == 1)):
outOfPlace = index
return arr
# Driver Code
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)))
# This code is contributed
# by Charan Sai
C#
// Rearrange array in alternating positive
// & negative items with O(1) extra space
using System;
class GFG {
// Utility function to right rotate
// all elements between [outofplace, cur]
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) {
// find the item which must be moved
// into the out-of-place entry if out-of-
// place entry is positive and current
// entry is negative OR if out-of-place
// entry is negative and current entry
// is negative then right rotate
// [...-3, -4, -5, 6...] --> [...6, -3, -4,
// -5...]
// ^ ^
// | |
// outofplace --> outofplace
//
if (((arr[index] >= 0)
&& (arr[outofplace] < 0))
|| ((arr[index] < 0)
&& (arr[outofplace] >= 0))) {
rightrotate(arr, n, outofplace, index);
// the new out-of-place entry
// is now 2 steps ahead
if (index - outofplace > 2)
outofplace = outofplace + 2;
else
outofplace = -1;
}
}
// if no entry has been flagged out-of-place
if (outofplace == -1) {
// check if current entry is out-of-place
if (((arr[index] >= 0)
&& ((index & 0x01) == 0))
|| ((arr[index] < 0)
&& (index & 0x01) == 1))
outofplace = index;
}
}
}
// A utility function to print an
// array 'arr[]' of size 'n'
static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
Console.WriteLine("");
}
// Driver code
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);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to rearrange positive and
// negative integers in alternate fashion
// while keeping the order of positive
// and negative numbers.
// Utility function to right rotate all
// elements between [outofplace, cur]
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)
{
// find the item which must be moved
// into the out-of-place entry if
// out-of-place entry is positive and
// current entry is negative OR if
// out-of-place entry is negative
// and current entry is negative then
// right rotate
// [...-3, -4, -5, 6...] --> [...6, -3, -4, -5...]
// ^ ^
// | |
// outofplace --> outofplace
//
if ((($arr[$index] >= 0) && ($arr[$outofplace] < 0)) ||
(($arr[$index] < 0) && ($arr[$outofplace] >= 0)))
{
rightrotate($arr, $n, $outofplace, $index);
// the new out-of-place entry is
// now 2 steps ahead
if ($index - $outofplace > 2)
$outofplace = $outofplace + 2;
else
$outofplace = -1;
}
}
// if no entry has been flagged out-of-place
if ($outofplace == -1)
{
// check if current entry is out-of-place
if ((($arr[$index] >= 0) && (!($index & 0x01)))
|| (($arr[$index] < 0) && ($index & 0x01)))
{
$outofplace = $index;
}
}
}
}
// A utility function to print an
// array 'arr[]' of size 'n'
function printArray(&$arr, $n)
{
for ($i = 0; $i < $n; $i++)
echo $arr[$i]." ";
echo "\n";
}
// Driver Code
// arr = array(-5, 3, 4, 5, -6, -2, 8, 9, -1, -4);
// arr = array(-5, -3, -4, -5, -6, 2 , 8, 9, 1 , 4);
// arr = array(5, 3, 4, 2, 1, -2 , -8, -9, -1 , -4);
// arr = array(-5, 3, -4, -7, -1, -2 , -8, -9, 1 , -4);
$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);
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// Utility function to right rotate all elements
// between [outofplace, cur]
function rightrotate(arr , n , outofplace , cur) {
var tmp = arr[cur];
for (i = cur; i > outofplace; i--)
arr[i] = arr[i - 1];
arr[outofplace] = tmp;
}
function rearrange(arr , n) {
var outofplace = -1;
for (var index = 0; index < n; index++)
{
if (outofplace >= 0)
{
// find the item which must be moved into
// the out-of-place entry if out-of-place
// entry is positive and current entry is
// negative OR if out-of-place entry is
// negative and current entry is negative
// then right rotate
//
// [...-3, -4, -5, 6...] --> [...6, -3,
// -4, -5...]
// ^ ^
// | |
// outofplace --> outofplace
//
if (((arr[index] >= 0) && (arr[outofplace] < 0)) || ((arr[index] < 0) && (arr[outofplace] >= 0))) {
rightrotate(arr, n, outofplace, index);
// the new out-of-place entry is now 2
// steps ahead
if (index - outofplace >= 2)
outofplace = outofplace + 2;
else
outofplace = -1;
}
}
// if no entry has been flagged out-of-place
if (outofplace == -1) {
// check if current entry is out-of-place
if (((arr[index] >= 0) && ((index & 0x01) == 0)) || ((arr[index] < 0) && (index & 0x01) == 1))
outofplace = index;
}
}
}
// A utility function to print
// an array 'arr' of size 'n'
function printArray(arr , n) {
for (i = 0; i < n; i++)
document.write(arr[i] + " ");
document.write("");
}
// Driver Code
/*
* var arr[n] = [-5, 3, 4, 5, -6, -2, 8, 9, -1, -4]; var arr = [-5, -3, -4,
* -5, -6, 2 , 8, 9, 1 , 4]; var arr = [5, 3, 4, 2, 1, -2 , -8, -9, -1 , -4];
* var arr = [-5, 3, -4, -7, -1, -2 , -8, -9, 1 , -4];
*/
var arr = [ -5, -2, 5, 2, 4, 7, 1, 8, 0, -8 ];
var n = arr.length;
document.write("Given array is ");
printArray(arr, n);
rearrange(arr, n);
document.write("<br/>RearrangeD array is ");
printArray(arr, n);
// This code is contributed by gauravrajput1
</script>
Producció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
Complejidad de tiempo: O (N ^ 2), ya que estamos usando un bucle para atravesar N veces y llamando a la función rightrotate cada vez, lo que costará O (N).
Complejidad espacial: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA