Dada una array, reorganice la array de manera que:
- Si el índice i es par, arr[i] <= arr[i+1]
- Si el índice i es impar, arr[i] >= arr[i+1]
Nota: Puede haber múltiples respuestas.
Ejemplos:
Input : arr[] = {2, 3, 4, 5}
Output : arr[] = {2, 4, 3, 5}
Explanation : Elements at even indexes are
smaller and elements at odd indexes are greater
than their next elements
Note : Another valid answer
is arr[] = {3, 4, 2, 5}
Input :arr[] = {6, 4, 2, 1, 8, 3}
Output :arr[] = {4, 6, 1, 8, 2, 3}
Este problema es similar a clasificar una array en la forma de onda .
- Una solución simple es ordenar la array en orden decreciente y luego, a partir del segundo elemento, intercambiar los elementos adyacentes.
- Una solución eficiente es iterar sobre la array e intercambiar los elementos según la condición dada.
Si tenemos una array de longitud n, iteramos desde el índice 0 hasta n-2 y verificamos la condición dada.
En cualquier momento, si i es par y arr[i] > arr[i+1], entonces intercambiamos arr[i] y arr[i+1]. De manera similar, si i es impar y
arr[i] < arr[i+1], entonces intercambiamos arr[i] y arr[i+1].
Para el ejemplo dado:
Before rearrange, arr[] = {2, 3, 4, 5}
Start iterating over the array till index 2 (as n = 4)
Primer paso:
en i = 0, arr[i] = 2 y arr[i+1] = 3. Como i es par y arr[i] < arr[i+1], no es necesario cambiar.
Segundo paso:
en i = 1, arr[i] = 3 y arr[i+1] = 4. Como i es impar y arr[i] < arr[i+1], cámbielos.
Ahora arr[] = {2, 4, 3, 5}
Tercer paso:
En i = 2, arr[i] = 3 y arr[i+1] = 5. Entonces, no es necesario cambiarlos
Después de reorganizar, arr[] = {2, 4, 3, 5}
diagrama de flujo
diagrama de flujo
Implementación:
C++
// CPP code to rearrange an array such that
// even index elements are smaller and odd
// index elements are greater than their
// next.
#include <iostream>
using namespace std;
void rearrange(int* arr, int n)
{
for (int i = 0; i < n - 1; i++) {
if (i % 2 == 0 && arr[i] > arr[i + 1])
swap(arr[i], arr[i + 1]);
if (i % 2 != 0 && arr[i] < arr[i + 1])
swap(arr[i], arr[i + 1]);
}
}
/* Utility that prints out an array in
a line */
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
/* Driver function to test above functions */
int main()
{
int arr[] = { 6, 4, 2, 1, 8, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Before rearranging: \n";
printArray(arr, n);
rearrange(arr, n);
cout << "After rearranging: \n";
printArray(arr, n);
return 0;
}
Java
// Java code to rearrange an array such
// that even index elements are smaller
// and odd index elements are greater
// than their next.
class GFG {
static void rearrange(int arr[], int n)
{
int temp;
for (int i = 0; i < n - 1; i++) {
if (i % 2 == 0 && arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
if (i % 2 != 0 && arr[i] < arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
/* Utility that prints out an array in
a line */
static void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 6, 4, 2, 1, 8, 3 };
int n = arr.length;
System.out.print("Before rearranging: \n");
printArray(arr, n);
rearrange(arr, n);
System.out.print("After rearranging: \n");
printArray(arr, n);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python code to rearrange
# an array such that
# even index elements
# are smaller and odd
# index elements are
# greater than their
# next.
def rearrange(arr, n):
for i in range(n - 1):
if (i % 2 == 0 and arr[i] > arr[i + 1]):
temp = arr[i]
arr[i]= arr[i + 1]
arr[i + 1]= temp
if (i % 2 != 0 and arr[i] < arr[i + 1]):
temp = arr[i]
arr[i]= arr[i + 1]
arr[i + 1]= temp
# Utility that prints out an array in
# a line
def printArray(arr, size):
for i in range(size):
print(arr[i], " ", end ="")
print()
# Driver code
arr = [ 6, 4, 2, 1, 8, 3 ]
n = len(arr)
print("Before rearranging: ")
printArray(arr, n)
rearrange(arr, n)
print("After rearranging:")
printArray(arr, n);
# This code is contributed
# by Anant Agarwal.
C#
// C# code to rearrange an array such
// that even index elements are smaller
// and odd index elements are greater
// than their next.
using System;
class GFG {
static void rearrange(int[] arr, int n)
{
int temp;
for (int i = 0; i < n - 1; i++) {
if (i % 2 == 0 && arr[i] > arr[i + 1])
{
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
if (i % 2 != 0 && arr[i] < arr[i + 1])
{
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
/* Utility that prints out an array in
a line */
static void printArray(int[] arr, int size)
{
for (int i = 0; i < size; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver code
public static void Main()
{
int[] arr = { 6, 4, 2, 1, 8, 3 };
int n = arr.Length;
Console.WriteLine("Before rearranging: ");
printArray(arr, n);
rearrange(arr, n);
Console.WriteLine("After rearranging: ");
printArray(arr, n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP code to rearrange an array such
// that even index elements are smaller
// and odd index elements are greater
// than their next.
function swap(&$a, &$b)
{
$temp = $a;
$a = $b;
$b = $temp;
}
function rearrange(&$arr, $n)
{
for ($i = 0; $i < $n - 1; $i++)
{
if ($i % 2 == 0 &&
$arr[$i] > $arr[$i + 1])
swap($arr[$i], $arr[$i + 1]);
if ($i % 2 != 0 &&
$arr[$i] < $arr[$i + 1])
swap($arr[$i], $arr[$i + 1]);
}
}
/* Utility that prints out
an array in a line */
function printArray(&$arr, $size)
{
for ($i = 0; $i < $size; $i++)
echo $arr[$i] . " ";
echo "\n";
}
// Driver Code
$arr = array(6, 4, 2, 1, 8, 3 );
$n = sizeof($arr);
echo "Before rearranging: \n";
printArray($arr, $n);
rearrange($arr, $n);
echo "After rearranging: \n";
printArray($arr, $n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// JavaScript code to rearrange an array such that
// even index elements are smaller and odd
// index elements are greater than their
// next.
let rearrange = (arr, n)=>{
for (let i = 0; i < n - 1; i++) {
if (i % 2 == 0 && arr[i] > arr[i + 1]){
// swap(arr[i], arr[i + 1]);
let temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
if (i % 2 != 0 && arr[i] < arr[i + 1]){
// swap(arr[i], arr[i + 1]);
let temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
}
// function to print array
let printArray = (arr, size)=>{
ans = '';
for (let i = 0; i < size; i++){
ans += arr[i] + " ";
}
document.write(ans);
}
// Driver Code
let arr = [ 6, 4, 2, 1, 8, 3 ];
let n = arr.length;
document.write("Before rearranging: ");
printArray(arr, n);
rearrange(arr, n);
document.write("<br>");
document.write("After rearranging: ");
printArray(arr, n);
</script>
Before rearranging: 6 4 2 1 8 3 After rearranging: 4 6 1 8 2 3
Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces,
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.
Este artículo es una contribución de Sukanta Nandi . 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.
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