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.
C
// A C++ program to put positive numbers at even indexes (0,
// 2, 4,..) and negative numbers at odd indexes (1, 3, 5, ..)
#include <stdio.h>
// prototype for swap
void swap(int *a, int *b);
// 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, ..).
void rearrange(int arr[], int 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.
int i = -1;
for (int 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
int 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
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// A utility function to print an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%4d ", arr[i]);
}
// Driver program to test above functions
int main()
{
int arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9};
int n = sizeof(arr)/sizeof(arr[0]);
rearrange(arr, n);
printArray(arr, n);
return 0;
}
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