Dada una array ordenada de enteros positivos, reorganice la array alternativamente, es decir, el primer elemento debe ser el valor máximo, el segundo valor mínimo, el tercer segundo máximo, el cuarto segundo mínimo y así sucesivamente.
Ejemplos:
Entrada : arr[] = {1, 2, 3, 4, 5, 6, 7}
Salida : arr[] = {7, 1, 6, 2, 5, 3, 4}
Entrada : arr[] = {1 , 2, 3, 4, 5, 6}
Salida : arr[] = {6, 1, 5, 2, 4, 3}
Hemos discutido una solución en la publicación a continuación:
Reorganizar una array en forma mínima máxima | Conjunto 1 : la solución discutida aquí requiere espacio adicional, cómo resolver este problema con O (1) espacio adicional.
En esta publicación se analiza una solución que requiere O(n) tiempo y O(1) espacio adicional. La idea es usar la multiplicación y el truco modular para almacenar dos elementos en un índice.
even index : remaining maximum element.
odd index : remaining minimum element.
max_index : Index of remaining maximum element
(Moves from right to left)
min_index : Index of remaining minimum element
(Moves from left to right)
Initialize: max_index = 'n-1'
min_index = 0
// can be any element which is more
// than the maximum value in array
max_element = arr[max_index] + 1
For i = 0 to n-1
If 'i' is even
arr[i] += arr[max_index] % max_element * max_element
max_index--
// if 'i' is odd
ELSE
arr[i] += arr[min_index] % max_element * max_element
min_index++
¿Cómo funciona la expresión “arr[i] += arr[max_index] % max_element * max_element” ?
El propósito de esta expresión es almacenar dos elementos en el índice arr[i]. arr[max_index] se almacena como multiplicador y “arr[i]” se almacena como resto. Por ejemplo, en {1 2 3 4 5 6 7 8 9}, max_element es 10 y almacenamos 91 en el índice 0. Con 91, podemos obtener el elemento original como 91%10 y el elemento nuevo como 91/10.
Debajo de la implementación de la idea anterior:
Java
// Java program to rearrange an
// array in minimum maximum form
public class Main {
// Prints max at first position, min
// at second position second max at
// third position, second min at
// fourth position and so on.
public static void rearrange(int arr[],
int n)
{
// Initialize index of first minimum
// and first maximum element
int max_idx = n - 1, min_idx = 0;
// Store maximum element of array
int max_elem = arr[n - 1] + 1;
// Traverse array elements
for (int i = 0; i < n; i++)
{
// At even index : we have to put
// maximum element
if (i % 2 == 0)
{
arr[i] += ((arr[max_idx] % max_elem) *
max_elem);
max_idx--;
}
// At odd index : we have to put
// minimum element
else
{
arr[i] += ((arr[min_idx] % max_elem) *
max_elem);
min_idx++;
}
}
// Array elements back to it's
// original form
for (int i = 0; i < n; i++)
arr[i] = arr[i] / max_elem;
}
// Driver code
public static void main(String args[])
{
int arr[] = {1, 2, 3, 4, 5,
6, 7, 8, 9};
int n = arr.length;
System.out.println(
"Original Array");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
rearrange(arr, n);
System.out.print(
"Modified Array");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// This code is contributed by Swetank Modi
Producción :
Original Array 1 2 3 4 5 6 7 8 9 Modified Array 9 1 8 2 7 3 6 4 5
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Gracias Saurabh Srivastava y Gaurav Ahirwar por sugerir este enfoque.
Otro enfoque: un enfoque más simple será observar el posicionamiento de indexación de elementos máximos y elementos mínimos. El índice par almacena los elementos máximos y el índice impar almacena los elementos mínimos. Con cada índice creciente, el elemento máximo disminuye en uno y el elemento mínimo aumenta en uno. Se puede realizar un recorrido simple y arr[] se puede completar de nuevo.
Nota: Este enfoque solo es válido cuando los elementos de una array ordenada dada son consecutivos, es decir, varían en una unidad.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program to rearrange an
// array in minimum maximum form
public class Main
{
// Prints max at first position, min
// at second position second max at
// third position, second min at
// fourth position and so on.
public static void rearrange(int arr[],
int n)
{
// Initialize index of first minimum
// and first maximum element
int max_ele = arr[n - 1];
int min_ele = arr[0];
// Traverse array elements
for (int i = 0; i < n; i++)
{
// At even index : we have to put
// maximum element
if (i % 2 == 0)
{
arr[i] = max_ele;
max_ele -= 1;
}
// At odd index : we have to put
// minimum element
else
{
arr[i] = min_ele;
min_ele += 1;
}
}
}
// Driver code
public static void main(String args[])
{
int arr[] = {1, 2, 3, 4, 5,
6, 7, 8, 9};
int n = arr.length;
System.out.println("Original Array");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
rearrange(arr, n);
System.out.print(
"Modified Array");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Producción :
Original Array 1 2 3 4 5 6 7 8 9 Modified Array 9 1 8 2 7 3 6 4 5
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Consulte el artículo completo sobre Reorganizar una array en forma máxima mínima | ¡Establezca 2 (O (1) espacio adicional) 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