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 <iostream> using namespace std; class GFG { public: void rearrange(int [],int); void swap(int *,int *); void printArray(int [],int); }; // 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 GFG :: 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 GFG :: swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // A utility function to print an array void GFG :: printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } // Driver Code int main() { int arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9}; int n = sizeof(arr) / sizeof(arr[0]); GFG test; test.rearrange(arr, n); test.printArray(arr, n); return 0; } // This code is contributed // by vt_Yogesh Shukla 1
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