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
max_element = arr[max_index] + 1 //can be any element which is more than the maximum value in array
For i = 0 to n-1
If 'i' is even
arr[i] += arr[max_index] % max_element * max_element
max_index--
ELSE // if 'i' is odd
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:
C++
// C++ program to rearrange an array in minimum
// maximum form
#include <bits/stdc++.h>
using namespace std;
// Prints max at first position, min at second position
// second max at third position, second min at fourth
// position and so on.
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 program to test above function
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original Arrayn";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
rearrange(arr, n);
cout << "\nModified Array\n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
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("\nModified Array\n");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// This code is contributed by Swetank Modi
Python3
# Python3 program to rearrange an
# array in minimum maximum form
# Prints max at first position, min at second position
# second max at third position, second min at fourth
# position and so on.
def rearrange(arr, n):
# Initialize index of first minimum
# and first maximum element
max_idx = n - 1
min_idx = 0
# Store maximum element of array
max_elem = arr[n-1] + 1
# Traverse array elements
for i in range(0, n) :
# At even index : we have to put maximum element
if i % 2 == 0 :
arr[i] += (arr[max_idx] % max_elem ) * max_elem
max_idx -= 1
# At odd index : we have to put minimum element
else :
arr[i] += (arr[min_idx] % max_elem ) * max_elem
min_idx += 1
# array elements back to it's original form
for i in range(0, n) :
arr[i] = arr[i] / max_elem
# Driver Code
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
n = len(arr)
print ("Original Array")
for i in range(0, n):
print (arr[i], end = " ")
rearrange(arr, n)
print ("\nModified Array")
for i in range(0, n):
print (int(arr[i]), end = " ")
# This code is contributed by Shreyanshi Arun.
C#
// C# program to rearrange an
// array in minimum maximum form
using System;
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()
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int n = arr.Length;
Console.WriteLine("Original Array");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
rearrange(arr, n);
Console.WriteLine("Modified Array");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to rearrange an
// array in minimum-maximum form
// Prints max at first position,
// min at second position
// second max at third position,
// second min at fourth
// position and so on.
function rearrange(&$arr, $n)
{
// initialize index of first
// minimum and first maximum element
$max_idx = $n - 1; $min_idx = 0;
// store maximum element of array
$max_elem = $arr[$n - 1] + 1;
// traverse array elements
for ($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 ($i = 0; $i < $n; $i++)
$arr[$i] = (int)($arr[$i] / $max_elem);
}
// Driver Code
$arr = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
$n = sizeof($arr);
echo "Original Array" . "\n";
for ($i = 0; $i < $n; $i++)
echo $arr[$i] . " ";
rearrange($arr, $n);
echo "\nModified Array\n";
for ($i = 0; $i < $n; $i++)
echo $arr[$i] . " ";
// This code is contributed
// by Akanksha Rai(Abby_akku)
Javascript
<script>
// JavaScript program to rearrange an array in minimum
// maximum form
// Prints max at first position, min at second position
// second max at third position, second min at fourth
// position and so on.
function rearrange(arr, n)
{
// initialize index of first minimum and first
// maximum element
let max_idx = n - 1, min_idx = 0;
// store maximum element of array
let max_elem = arr[n - 1] + 1;
// traverse array elements
for (let 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 (let i = 0; i < n; i++)
arr[i] = Math.floor(arr[i] / max_elem);
}
// Driver program to test above function
let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
let n = arr.length;
document.write("Original Array<br>");
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
rearrange(arr, n);
document.write("<br>Modified Array<br>");
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by Surbhi Tyagi.
</script>
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)
Espacio Auxiliar: O(1), ya que no se utiliza espacio extra
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:
C++
// C++ program to rearrange an array in minimum
// maximum form
#include <bits/stdc++.h>
using namespace std;
// Prints max at first position, min at second position
// second max at third position, second min at fourth
// position and so on.
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 program to test above function
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original Array\n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
rearrange(arr, n);
cout << "\nModified Array\n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
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("\nModified Array\n");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Python3
# Python 3 program to rearrange an
# array in minimum maximum form
# Prints max at first position, min
# at second position second max at
# third position, second min at
# fourth position and so on.
def rearrange(arr, n):
# initialize index of first minimum
# and first maximum element
max_ele = arr[n - 1]
min_ele = arr[0]
# traverse array elements
for i in range(n):
# 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
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
n = len(arr)
print("Original Array")
for i in range(n):
print(arr[i], end = " ")
rearrange(arr, n)
print("\nModified Array")
for i in range(n):
print(arr[i], end = " ")
# This code is contributed by Shrikant13
C#
// C# program to rearrange
// an array in minimum
// maximum form
using System;
class GFG
{
// 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
static public void Main ()
{
int []arr = {1, 2, 3, 4,
5, 6, 7, 8, 9};
int n = arr.Length;
Console.WriteLine("Original Array");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
rearrange(arr, n);
Console.Write("\nModified Array\n");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by ajit
Javascript
<script>
// Javascript program to rearrange an array in minimum
// maximum form
// Prints max at first position, min at second
// position second max at third position, second
// min at fourth position and so on.
function rearrange(arr, n)
{
// initialize index of first minimum and first
// maximum element
let max_ele = arr[n - 1];
let min_ele = arr[0];
// traverse array elements
for (let 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
let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
let n = arr.length;
document.write("Original Array" + "<br />");
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
document.write("<br />");
rearrange(arr, n);
document.write("\nModified Array\n" + "<br />");
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
</script>
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)
Espacio Auxiliar: O(1), ya que no se utiliza espacio extra
Gracias Apollo Doley por sugerir este enfoque.
Este artículo es una contribución de Aarti_Rathi Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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