Dada una array arr[] de N enteros positivos con igual número de elementos pares e impares. La tarea es usar el intercambio en el lugar para intercambiar posiciones de elementos pares e impares en la array.
Ejemplos:
Entrada: arr[] = {1, 3, 2, 4}
Salida: 2 4 1 3
Explicación:
antes de reorganizar la array dada, los índices 0 y 1 tenían elementos impares y los índices 2 y 3 tenían elementos pares.
Después de la reorganización, la array se convierte en {2, 4, 1, 3} donde los índices 0 y 1 tienen elementos pares y los índices 2 y 3 tienen elementos impares.Entrada: arr[] = {2, 2, 1, 3}
Salida: 1 3 2 2
Explicación:
antes de reorganizar la array dada, los índices 0 y 1 tenían elementos pares y los índices 2 y 3 tenían elementos impares.
Después de la reorganización, la array se convierte en {1, 3, 2, 2} donde los índices 0 y 1 tienen elementos impares y los índices 2 y 3 tienen elementos pares.
Enfoque ingenuo: el enfoque más simple es iterar sobre los elementos de la array usando dos bucles, el bucle externo selecciona cada elemento de la array y el bucle interno es encontrar el elemento de paridad opuesto para el elemento seleccionado e intercambiarlos. Después de intercambiar elementos, marque el elemento elegido como negativo para no volver a elegirlo. Finalmente, haga que todos los elementos sean positivos e imprima la array.
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 replace each even
// element by odd and vice-versa
// in a given array
void replace(int arr[], int n)
{
// Traverse array
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// If current element is even
// then swap it with odd
if (arr[i] >= 0 && arr[j] >= 0 &&
arr[i] % 2 == 0 &&
arr[j] % 2 != 0)
{
// Perform Swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// Change the sign
arr[j] = -arr[j];
break;
}
// If current element is odd
// then swap it with even
else if (arr[i] >= 0 && arr[j] >= 0 &&
arr[i] % 2 != 0 &&
arr[j] % 2 == 0)
{
// Perform Swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// Change the sign
arr[j] = -arr[j];
break;
}
}
}
// Marked element positive
for(int i = 0; i < n; i++)
arr[i] = abs(arr[i]);
// Print final array
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 3, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
replace(arr,n);
}
// This code is contributed by SURENDRA_GANGWAR
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to replace each even
// element by odd and vice-versa
// in a given array
static void replace(int[] arr)
{
// Stores length of array
int n = arr.length;
// Traverse array
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// If current element is even
// then swap it with odd
if (arr[i] >= 0
&& arr[j] >= 0
&& arr[i] % 2 == 0
&& arr[j] % 2 != 0) {
// Perform Swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// Change the sign
arr[j] = -arr[j];
break;
}
// If current element is odd
// then swap it with even
else if (arr[i] >= 0
&& arr[j] >= 0
&& arr[i] % 2 != 0
&& arr[j] % 2 == 0) {
// Perform Swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// Change the sign
arr[j] = -arr[j];
break;
}
}
}
// Marked element positive
for (int i = 0; i < n; i++)
arr[i] = Math.abs(arr[i]);
// Print final array
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 1, 3, 2, 4 };
// Function Call
replace(arr);
}
}
Python3
# Python3 program for the # above approach # Function to replace each even # element by odd and vice-versa # in a given array def replace(arr, n): # Traverse array for i in range(n): for j in range(i + 1, n): # If current element is # even then swap it with odd if (arr[i] >= 0 and arr[j] >= 0 and arr[i] % 2 == 0 and arr[j] % 2 != 0): # Perform Swap tmp = arr[i] arr[i] = arr[j] arr[j] = tmp # Change the sign arr[j] = -arr[j] break # If current element is odd # then swap it with even elif (arr[i] >= 0 and arr[j] >= 0 and arr[i] % 2 != 0 and arr[j] % 2 == 0): # Perform Swap tmp = arr[i] arr[i] = arr[j] arr[j] = tmp # Change the sign arr[j] = -arr[j] break # Marked element positive for i in range(n): arr[i] = abs(arr[i]) # Print final array for i in range(n): print(arr[i], end = " ") # Driver Code if __name__ == "__main__": # Given array arr[] arr = [1, 3, 2, 4] n = len(arr) # Function Call replace(arr, n) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function to replace each even
// element by odd and vice-versa
// in a given array
static void replace(int[] arr)
{
// Stores length of array
int n = arr.Length;
// Traverse array
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// If current element is even
// then swap it with odd
if (arr[i] >= 0 &&
arr[j] >= 0 &&
arr[i] % 2 == 0 &&
arr[j] % 2 != 0)
{
// Perform Swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// Change the sign
arr[j] = -arr[j];
break;
}
// If current element is odd
// then swap it with even
else if (arr[i] >= 0 &&
arr[j] >= 0 &&
arr[i] % 2 != 0 &&
arr[j] % 2 == 0)
{
// Perform Swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// Change the sign
arr[j] = -arr[j];
break;
}
}
}
// Marked element positive
for(int i = 0; i < n; i++)
arr[i] = Math.Abs(arr[i]);
// Print readonly array
for(int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = { 1, 3, 2, 4 };
// Function Call
replace(arr);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to replace each even
// element by odd and vice-versa
// in a given array
function replace(arr)
{
// Stores length of array
let n = arr.length;
// Traverse array
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// If current element is even
// then swap it with odd
if (arr[i] >= 0
&& arr[j] >= 0
&& arr[i] % 2 == 0
&& arr[j] % 2 != 0) {
// Perform Swap
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// Change the sign
arr[j] = -arr[j];
break;
}
// If current element is odd
// then swap it with even
else if (arr[i] >= 0
&& arr[j] >= 0
&& arr[i] % 2 != 0
&& arr[j] % 2 == 0) {
// Perform Swap
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// Change the sign
arr[j] = -arr[j];
break;
}
}
}
// Marked element positive
for (let i = 0; i < n; i++)
arr[i] = Math.abs(arr[i]);
// Print final array
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver Code
// Given array arr[]
let arr = [ 1, 3, 2, 4 ];
// Function Call
replace(arr);
</script>
Producción
2 4 1 3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el enfoque de dos punteros . Recorra la array seleccionando cada elemento que sea mayor que 0 y busque el elemento de paridad opuesto mayor que 0 desde el índice actual hasta el final de la array. Si lo encuentra, intercambie los elementos y multiplíquelos por -1 . Siga los pasos a continuación para resolver el problema:
- Inicialice las variables e y o con -1 que almacenará el número par e impar encontrado actualmente, respectivamente, que aún no se ha tomado.
- Recorra la array dada sobre el rango [0, N – 1] y haga lo siguiente:
- Elija el elemento arr[i] si es mayor que 0 .
- Si arr[i] es par, incrementa o + 1 en 1 y encuentra el siguiente número impar que aún no está marcado. Marque el número actual y el encontrado multiplicándolos por -1 e intercámbielos.
- Si arr[i] es impar, incrementa e + 1 en 1 y encuentra el siguiente número par que aún no está marcado. Marque el número actual y el encontrado multiplicándolos por -1 e intercámbielos.
- Después de recorrer toda la array, multiplique sus elementos con -1 para volver a hacerlos positivos e imprimir esa array.
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;
#define N 3
#define M 4
// Function to replace odd elements
// with even elements and vice versa
void swapEvenOdd(int arr[], int n)
{
int o = -1, e = -1;
// Traverse the given array
for(int i = 0; i < n; i++)
{
// If arr[i] is visited
if (arr[i] < 0)
continue;
int r = -1;
if (arr[i] % 2 == 0)
{
o++;
// Find the next odd element
while (arr[o] % 2 == 0 || arr[o] < 0)
o++;
r = o;
}
else
{
e++;
// Find next even element
while (arr[e] % 2 == 1 || arr[e] < 0)
e++;
r = e;
}
// Mark them visited
arr[i] *= -1;
arr[r] *= -1;
// Swap them
int tmp = arr[i];
arr[i] = arr[r];
arr[r] = tmp;
}
// Print the final array
for(int i = 0; i < n; i++)
{
cout << (-1 * arr[i]) << " ";
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 3, 2, 4 };
// Length of the array
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
swapEvenOdd(arr, n);
}
// This code is contributed by Rajput-Ji
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to replace odd elements
// with even elements and vice versa
static void swapEvenOdd(int arr[])
{
// Length of the array
int n = arr.length;
int o = -1, e = -1;
// Traverse the given array
for (int i = 0; i < n; i++) {
// If arr[i] is visited
if (arr[i] < 0)
continue;
int r = -1;
if (arr[i] % 2 == 0) {
o++;
// Find the next odd element
while (arr[o] % 2 == 0
|| arr[o] < 0)
o++;
r = o;
}
else {
e++;
// Find next even element
while (arr[e] % 2 == 1
|| arr[e] < 0)
e++;
r = e;
}
// Mark them visited
arr[i] *= -1;
arr[r] *= -1;
// Swap them
int tmp = arr[i];
arr[i] = arr[r];
arr[r] = tmp;
}
// Print the final array
for (int i = 0; i < n; i++) {
System.out.print(
(-1 * arr[i]) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 3, 2, 4 };
// Function Call
swapEvenOdd(arr);
}
}
Python3
# Python3 program for the above approach # Function to replace odd elements # with even elements and vice versa def swapEvenOdd(arr): # Length of the array n = len(arr) o = -1 e = -1 # Traverse the given array for i in range(n): # If arr[i] is visited if (arr[i] < 0): continue r = -1 if (arr[i] % 2 == 0): o += 1 # Find the next odd element while (arr[o] % 2 == 0 or arr[o] < 0): o += 1 r = o else: e += 1 # Find next even element while (arr[e] % 2 == 1 or arr[e] < 0): e += 1 r = e # Mark them visited arr[i] *= -1 arr[r] *= -1 # Swap them tmp = arr[i] arr[i] = arr[r] arr[r] = tmp # Print the final array for i in range(n): print((-1 * arr[i]), end = " ") # Driver Code if __name__ == '__main__': # Given array arr arr = [ 1, 3, 2, 4 ] # Function Call swapEvenOdd(arr) # This code is contributed by Amit Katiyar
C#
// C# program for the above approach
using System;
class GFG{
// Function to replace odd elements
// with even elements and vice versa
static void swapEvenOdd(int []arr)
{
// Length of the array
int n = arr.Length;
int o = -1, e = -1;
// Traverse the given array
for(int i = 0; i < n; i++)
{
// If arr[i] is visited
if (arr[i] < 0)
continue;
int r = -1;
if (arr[i] % 2 == 0)
{
o++;
// Find the next odd element
while (arr[o] % 2 == 0 ||
arr[o] < 0)
o++;
r = o;
}
else
{
e++;
// Find next even element
while (arr[e] % 2 == 1 ||
arr[e] < 0)
e++;
r = e;
}
// Mark them visited
arr[i] *= -1;
arr[r] *= -1;
// Swap them
int tmp = arr[i];
arr[i] = arr[r];
arr[r] = tmp;
}
// Print the readonly array
for(int i = 0; i < n; i++)
{
Console.Write((-1 * arr[i]) + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 1, 3, 2, 4 };
// Function Call
swapEvenOdd(arr);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to replace odd elements
// with even elements and vice versa
function swapEvenOdd(arr, n)
{
let o = -1, e = -1;
// Traverse the given array
for(let i = 0; i < n; i++)
{
// If arr[i] is visited
if (arr[i] < 0)
continue;
let r = -1;
if (arr[i] % 2 == 0)
{
o++;
// Find the next odd element
while (arr[o] % 2 == 0 || arr[o] < 0)
o++;
r = o;
}
else
{
e++;
// Find next even element
while (arr[e] % 2 == 1 || arr[e] < 0)
e++;
r = e;
}
// Mark them visited
arr[i] *= -1;
arr[r] *= -1;
// Swap them
let tmp = arr[i];
arr[i] = arr[r];
arr[r] = tmp;
}
// Print the final array
for(let i = 0; i < n; i++)
{
document.write((-1 * arr[i]) + " ");
}
}
// Driver Code
// Given array arr[]
let arr = [ 1, 3, 2, 4 ];
// Length of the array
let n = arr.length;
// Function Call
swapEvenOdd(arr, n);
//This code is contributed by Mayank Tyagi
</script>
Producción
2 4 1 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente 2:
Otra forma de hacer esto sería usando una pila . Siga los pasos a continuación:
- Tome el elemento en el índice de la array arr[] y empújelo a una pila
- Iterar arr[] desde el índice i = 1 hasta el final y hacer lo siguiente:
- Si arr[i] y el elemento en la parte superior de la pila no son ni pares ni impares, extraiga e intercambie
- De lo contrario, empuje el elemento para apilar
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 replace odd elements
// with even elements and vice versa
void swapEvenOdd(int arr[], int N)
{
stack<pair<int, int> > stack;
// Push the first element to stack
stack.push({ 0, arr[0] });
// iterate the array and swap even and odd
for (int i = 1; i < N; i++)
{
if (!stack.empty())
{
if (arr[i] % 2 != stack.top().second % 2)
{
// pop and swap
pair<int, int> pop = stack.top();
stack.pop();
int index = pop.first, val = pop.second;
arr[index] = arr[i];
arr[i] = val;
}
else
stack.push({ i, arr[i] });
}
else
stack.push({ i, arr[i] });
}
// print the arr[]
for (int i = 0; i < N; i++)
cout << arr[i] << " ";
}
// Driven Program
int main()
{
// Given array arr[]
int arr[] = { 1, 3, 2, 4 };
// Stores the length of array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
swapEvenOdd(arr, N);
return 0;
}
// This code is contributed by Kingash.
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to replace odd elements
// with even elements and vice versa
static void swapEvenOdd(int arr[], int N)
{
Stack<int[]> stack = new Stack<>();
// Push the first element to stack
stack.push(new int[] { 0, arr[0] });
// iterate the array and swap even and odd
for (int i = 1; i < N; i++)
{
if (!stack.isEmpty())
{
if (arr[i] % 2 != stack.peek()[1] % 2)
{
// pop and swap
int pop[] = stack.pop();
int index = pop[0], val = pop[1];
arr[index] = arr[i];
arr[i] = val;
}
else
stack.push(new int[] { i, arr[i] });
}
else
stack.push(new int[] { i, arr[i] });
}
// print the arr[]
for (int i = 0; i < N; i++)
System.out.print(arr[i] + " ");
}
// Driver code
public static void main(String[] args)
{
// Given array arr
int arr[] = { 1, 3, 2, 4 };
// length of the arr
int N = arr.length;
// Function Call
swapEvenOdd(arr, N);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to replace odd elements # with even elements and vice versa def swapEvenOdd(arr): stack = [] # Push the first element to stack stack.append((0, arr[0],)) # iterate the array and swap even and odd for i in range(1, len(arr)): if stack: if arr[i]%2 != stack[-1][1]%2: #pop and swap index, val = stack.pop(-1) arr[index] = arr[i] arr[i] = val else: stack.append((i, arr[i],)) else: stack.append((i, arr[i],)) return arr # Driver Code if __name__ == '__main__': # Given array arr arr = [ 1, 3, 2, 4 ] # Function Call print(swapEvenOdd(arr)) # This code is contributed by Arunabha Choudhury
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to replace odd elements
// with even elements and vice versa
static void swapEvenOdd(int []arr, int N) {
Stack<int[]> stack = new Stack<int[]>();
// Push the first element to stack
stack.Push(new int[] { 0, arr[0] });
// iterate the array and swap even and odd
for (int i = 1; i < N; i++)
{
if (stack.Count != 0)
{
if (arr[i] % 2 != stack.Peek()[1] % 2)
{
// pop and swap
int []pop = stack.Pop();
int index = pop[0], val = pop[1];
arr[index] = arr[i];
arr[i] = val;
}
else
stack.Push(new int[] { i, arr[i] });
}
else
stack.Push(new int[] { i, arr[i] });
}
// print the []arr
for (int i = 0; i < N; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
// Given array arr
int []arr = { 1, 3, 2, 4 };
// length of the arr
int N = arr.Length;
// Function Call
swapEvenOdd(arr, N);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to replace odd elements
// with even elements and vice versa
function swapEvenOdd(arr, N)
{
let stack = [];
// Push the first element to stack
stack.push([0, arr[0]]);
// Iterate the array and swap even and odd
for(let i = 1; i < N; i++)
{
if (stack.length != 0)
{
if (arr[i] % 2 !=
stack[stack.length - 1][1] % 2)
{
// pop and swap
let pop = stack.pop();
let index = pop[0], val = pop[1];
arr[index] = arr[i];
arr[i] = val;
}
else
stack.push([i, arr[i]]);
}
else
stack.push([i, arr[i]]);
}
// print the arr[]
for(let i = 0; i < N; i++)
document.write(arr[i] + " ");
}
// Driver code
// Given array arr
let arr = [ 1, 3, 2, 4 ];
// Length of the arr
let N = arr.length;
// Function Call
swapEvenOdd(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
[4, 2, 3, 1]
Complejidad temporal: O(N)
Espacio auxiliar: O(N)