Una array contiene números positivos y negativos en orden aleatorio. Reorganice los elementos de la array para que los números positivos y negativos se coloquen alternativamente. 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.
Por ejemplo, si la array de entrada es [-1, 2, -3, 4, 5, 6, -7, 8, 9], la salida debería ser [9, -7, 8, -3, 5, – 1, 2, 4, 6]
Nota: El proceso de partición cambia el orden relativo de los elementos. Es decir, con este enfoque no se mantiene el orden de aparición de los elementos. Vea esto para mantener el orden de aparición de los elementos en este problema.
La solución es separar primero los números positivos y negativos usando el proceso de partición de QuickSort. En el proceso de partición, considere 0 como valor del elemento pivote para que todos los números negativos se coloquen antes de los números positivos. Una vez que se separan los números negativos y positivos, comenzamos con el primer número negativo y el primer número positivo e intercambiamos cada número negativo alternativo con el siguiente número positivo.
PHP
<?php
// A PHP program to put positive numbers
// at even indexes (0, 2, 4,..) and negative
// numbers at odd indexes (1, 3, 5, ..)
// The main function that rearranges elements
// of given array. It puts positive elements
// at even indexes (0, 2, ..) and negative
// numbers at odd indexes (1, 3, ..).
function rearrange(&$arr, $n)
{
// The following few lines are similar
// to partition process of QuickSort.
// The idea is to consider 0 as pivot
// and divide the array around it.
$i = -1;
for ($j = 0; $j < $n; $j++)
{
if ($arr[$j] < 0)
{
$i++;
swap($arr[$i], $arr[$j]);
}
}
// Now all positive numbers are at end and
// negative numbers at the beginning of array.
// Initialize indexes for starting point of
// positive and negative numbers to be swapped
$pos = $i + 1;
$neg = 0;
// Increment the negative index by 2 and
// positive index by 1, i.e., swap every
// alternate negative number with next
// positive number
while ($pos < $n && $neg < $pos &&
$arr[$neg] < 0)
{
swap($arr[$neg], $arr[$pos]);
$pos++;
$neg += 2;
}
}
// A utility function to swap two elements
function swap(&$a, &$b)
{
$temp = $a;
$a = $b;
$b = $temp;
}
// A utility function to print an array
function printArray(&$arr, $n)
{
for ($i = 0; $i < $n; $i++)
echo " " . $arr[$i] . " ";
}
// Driver Code
$arr = array(-1, 2, -3, 4, 5, 6, -7, 8, 9);
$n = count($arr);
rearrange($arr, $n);
printArray($arr, $n);
// This code is contributed
// by rathbhupendra
?>
Producción:
4 -3 5 -1 6 -7 2 8 9
Complejidad de tiempo: O (n) donde n es el número de elementos en una array dada. Como estamos usando un bucle para atravesar N veces, nos costará O (N) tiempo
Espacio auxiliar: O (1), ya que no estamos usando ningún espacio adicional.
Consulte el artículo completo sobre Reorganizar números positivos y negativos en tiempo O(n) y espacio adicional O(1) para obtener más detalles.
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