Dada una array ordenada arr[] que consta de N enteros positivos, la tarea es reorganizar la array de modo que todos los elementos de índices impares estén antes que todos los elementos de índices pares.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Salida: 2 4 6 8 1 3 5 7 9Entrada: arr[] = {0, 3, 7, 7, 10}
Salida: 3 7 0 7 10
Enfoque: el problema dado se puede resolver modificando la array dada tomando el valor ( elemento de array máximo + 1) como el pivote (digamos) y luego para la primera mitad de la array agregue el valor (arr[oddIndex]%pivot) *pivote en los índices impares oddIndex y para la segunda mitad de la array agregue el valor (arr[evenIndex]%pivot)*pivote en los índices pares evenIndex . Después de los pasos anteriores, divida cada elemento de la array por el valor de pivote . A continuación se muestra la ilustración de la misma:
Considere la array arr[] = {3, 7}, luego el valor de pivote es 7 + 1 = 8.
Para la primera mitad:
modifique el elemento de array arr[0] = 3 + (7%8)*8 = 3+ 56 = 59.Para la segunda mitad:
Modifique el elemento de array arr[1] = 7 + (59%8)*8 = 7 + 24 = 31.
Dividir cada elemento de la array por el pivote modifica la array a {7, 3}, que es el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the array
void printTheArray(int arr[], int N)
{
for (int i = 0; i < N; i++)
cout << arr[i] << " ";
}
// Function to rearrange the array such
// that odd indexed elements come before
// even indexed elements
void rearrange(int arr[], int N)
{
//Reduces the size of array by one
//because last element does not need
//to be changed in case N = odd
if (N & 1)
N--;
// Initialize the variables
int odd_idx = 1, even_idx = 0;
int i, max_elem = arr[N - 1] + 1;
// Iterate over the range
for (i = 0; i < N / 2; i++) {
// Add the modified element at
// the odd position
arr[i] += (arr[odd_idx] % max_elem) * max_elem;
odd_idx += 2;
}
// Iterate over the range
for (; i < N; i++) {
// Add the modified element at
// the even position
arr[i] += (arr[even_idx] % max_elem) * max_elem;
even_idx += 2;
}
// Iterate over the range
for (int i = 0; i < N; i++) {
// Divide by the maximum element
arr[i] = arr[i] / max_elem;
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 16, 18, 19 };
int N = sizeof(arr) / sizeof(arr[0]);
rearrange(arr, N);
printTheArray(arr, N);
return 0;
}
//This code is contributed by Akash Jha
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to print the array
static void printTheArray(int arr[], int N)
{
for (int i = 0; i < N; i++)
System.out.print(arr[i] + " ");
}
// Function to rearrange the array such
// that odd indexed elements come before
// even indexed elements
static void rearrange(int arr[], int N)
{
// Reduces the size of array by one
// because last element does not need
// to be changed in case N = odd
if ((N & 1) != 0)
N--;
// Initialize the variables
int odd_idx = 1, even_idx = 0;
int i, max_elem = arr[N - 1] + 1;
// Iterate over the range
for (i = 0; i < N / 2; i++) {
// Add the modified element at
// the odd position
arr[i] += (arr[odd_idx] % max_elem) * max_elem;
odd_idx += 2;
}
// Iterate over the range
for (; i < N; i++) {
// Add the modified element at
// the even position
arr[i] += (arr[even_idx] % max_elem) * max_elem;
even_idx += 2;
}
// Iterate over the range
for (i = 0; i < N; i++) {
// Divide by the maximum element
arr[i] = arr[i] / max_elem;
}
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, 16, 18, 19 };
int N = arr.length;
rearrange(arr, N);
printTheArray(arr, N);
}
}
// This code is contributed by avijitmondal1998.
Python3
# Python program for the above approach
# Function to print the array
def printArray(arr, n):
for i in range(N):
print(arr[i],end=" ")
print("\n")
# Function to rearrange the array such
# that odd indexed elements come before
# even indexed elements
def rearrange(arr, N):
#Reduces the size of array by one
#because last element does not need
#to be changed in case N = odd
if (N & 1):
N-=1
# Initialize the variables
odd_idx = 1
even_idx = 0
max_elem = arr[N - 1] + 1
# Iterate over the range
for i in range(N//2):
# Add the modified element at
# the odd position
arr[i] += (arr[odd_idx] % max_elem) * max_elem
odd_idx += 2
# Iterate over the range
for i in range(N//2,N):
# Add the modified element at
# the even position
arr[i] += (arr[even_idx] % max_elem) * max_elem
even_idx += 2
# Iterate over the range
for i in range(N):
# Divide by the maximum element
arr[i] = arr[i] // max_elem
# Driver Code
if __name__=="__main__":
arr = [ 1, 2, 3, 4, 5, 16, 18, 19 ]
N = len(arr)
rearrange(arr, N)
printArray(arr, N);
#This code is contributed by Akash Jha
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print the array
static void printTheArray(int []arr, int N)
{
for (int i = 0; i < N; i++)
Console.Write(arr[i]+" ");
}
// Function to rearrange the array such
// that odd indexed elements come before
// even indexed elements
static void rearrange(int []arr, int N)
{
// Reduces the size of array by one
// because last element does not need
// to be changed in case N = odd
if ((N & 1) != 0)
N--;
// Initialize the variables
int odd_idx = 1, even_idx = 0;
int i, max_elem = arr[N - 1] + 1;
// Iterate over the range
for (i = 0; i < N / 2; i++) {
// Add the modified element at
// the odd position
arr[i] += (arr[odd_idx] % max_elem) * max_elem;
odd_idx += 2;
}
// Iterate over the range
for (; i < N; i++) {
// Add the modified element at
// the even position
arr[i] += (arr[even_idx] % max_elem) * max_elem;
even_idx += 2;
}
// Iterate over the range
for(i = 0; i < N; i++) {
// Divide by the maximum element
arr[i] = arr[i] / max_elem;
}
}
// Driver Code
public static void Main()
{
int []arr = { 1, 2, 3, 4, 5, 16, 18, 19};
int N = arr.Length;
rearrange(arr, N);
printTheArray(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to print the array
function printTheArray(arr, N)
{
for (let i = 0; i < N; i++)
document.write(Math.floor(arr[i]) + " ");
}
// Function to rearrange the array such
// that odd indexed elements come before
// even indexed elements
function rearrange(arr, N)
{
// Reduces the size of array by one
// because last element does not need
// to be changed in case N = odd
if (N & 1)
N--;
// Initialize the variables
let odd_idx = 1, even_idx = 0;
let i, max_elem = arr[N - 1] + 1;
// Iterate over the range
for (i = 0; i < N / 2; i++) {
// Add the modified element at
// the odd position
arr[i] += (arr[odd_idx] % max_elem) * max_elem;
odd_idx += 2;
}
// Iterate over the range
for (; i < N; i++) {
// Add the modified element at
// the even position
arr[i] += (arr[even_idx] % max_elem) * max_elem;
even_idx += 2;
}
// Iterate over the range
for (let i = 0; i < N; i++) {
// Divide by the maximum element
arr[i] = arr[i] / max_elem;
}
}
// Driver Code
let arr =[ 1, 2, 3, 4, 5, 16, 18, 19 ];
let N = arr.length;
rearrange(arr, N);
printTheArray(arr, N);
// This code is contributed by _saurabh_jaiswal.
</script>
2 4 16 19 1 3 5 18
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.
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA