Dada una array arr[] de enteros, separe los números pares e impares en la array. De modo que todos los números pares deben estar presentes primero y luego los números impares.
Ejemplos:
Entrada: arr[] =1 9 5 3 2 6 7 11
Salida: 2 6 5 3 1 9 7 11Entrada: arr[] = 1 3 2 4 7 6 9 10
Salida: 2 4 6 10 7 1 9 3
Hemos discutido dos enfoques diferentes en las siguientes publicaciones:
Solución de fuerza bruta:
Como necesitamos mantener el orden de los elementos, esto se puede hacer en los siguientes pasos:
- Cree una array temporal A de tamaño n y un índice entero que mantendrá el índice de elementos insertados.
- Inicialice el índice con cero e itere sobre la array original y, si se encuentra un número par, coloque ese número en A [índice] y luego incremente el valor del índice.
- Vuelva a iterar sobre la array y, si se encuentra un número impar, colóquelo en A [índice] y luego incremente el valor del índice.
- Itere sobre la array temporal A y copie sus valores en la array original.
C++
// C++ Implementation of the above approach
#include <iostream>
using namespace std;
void arrayEvenAndOdd(int arr[], int n)
{
int a[n], index = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] % 2 == 0)
{
a[index] = arr[i];
index++;
}
}
for (int i = 0; i < n; i++)
{
if (arr[i] % 2 != 0)
{
a[index] = arr[i];
index++;
}
}
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 2, 4, 7, 6, 9, 10 };
int n = sizeof(arr) / sizeof(int);
// Function call
arrayEvenAndOdd(arr, n);
return 0;
}
Java
// Java Implementation of the above approach
import java.io.*;
class GFG
{
public static void arrayEvenAndOdd(int arr[], int n)
{
int[] a;
a = new int[n];
int index = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] % 2 == 0)
{
a[index] = arr[i];
index++;
}
}
for (int i = 0; i < n; i++)
{
if (arr[i] % 2 != 0)
{
a[index] = arr[i];
index++;
}
}
for (int i = 0; i < n; i++)
{
System.out.print(a[i] + " ");
}
System.out.println("");
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 3, 2, 4, 7, 6, 9, 10 };
int n = arr.length;
// Function call
arrayEvenAndOdd(arr, n);
}
}
// This code is contributed by rohitsingh07052.
Python3
# Python3 implementation of the above approach def arrayEvenAndOdd(arr, n): index = 0; a = [0 for i in range(n)] for i in range(n): if (arr[i] % 2 == 0): a[index] = arr[i] ind += 1 for i in range(n): if (arr[i] % 2 != 0): a[index] = arr[i] ind += 1 for i in range(n): print(a[i], end = " ") print() # Driver code arr = [ 1, 3, 2, 4, 7, 6, 9, 10 ] n = len(arr) # Function call arrayEvenAndOdd(arr, n) # This code is contributed by rohitsingh07052
C#
// C# implementation of the above approach
using System;
class GFG{
static void arrayEvenAndOdd(int[] arr, int n)
{
int[] a = new int[n];
int index = 0;
for(int i = 0; i < n; i++)
{
if (arr[i] % 2 == 0)
{
a[index] = arr[i];
index++;
}
}
for(int i = 0; i < n; i++)
{
if (arr[i] % 2 != 0)
{
a[index] = arr[i];
index++;
}
}
for(int i = 0; i < n; i++)
{
Console.Write(a[i] + " ");
}
}
// Driver code
static public void Main()
{
int[] arr = { 1, 3, 2, 4, 7, 6, 9, 10 };
int n = arr.Length;
arrayEvenAndOdd(arr, n);
}
}
// This code is contributed by Potta Lokesh
Javascript
<script>
// JavaScript Implementation of the above approach
function arrayEvenAndOdd(arr, n){
let a= [];
let index = 0;
for (let i = 0; i < n; i++)
{
if (arr[i] % 2 == 0)
{
a[index] = arr[i];
index++;
}
}
for (let i = 0; i < n; i++)
{
if (arr[i] % 2 != 0)
{
a[index] = arr[i];
index++;
}
}
for (let i = 0; i < n; i++)
{
document.write(a[i] +" ");
}
document.write('\n');
}
// Driver code
let arr = [ 1, 3, 2, 4, 7, 6, 9, 10 ];
let n = arr.length;
// Function call
arrayEvenAndOdd(arr, n);
</script>
Producción
2 4 6 10 1 3 7 9
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Enfoque eficiente:
La optimización para el enfoque anterior se basa en el esquema de partición de Lomuto.
- Mantenga un puntero a la posición antes del primer elemento impar en la array.
- Recorra la array y, si se encuentra un número par, cámbielo por el primer elemento impar.
- Continuar el recorrido.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP code to segregate even odd
// numbers in an array
#include <bits/stdc++.h>
using namespace std;
// Function to segregate even odd numbers
void arrayEvenAndOdd(int arr[], int n)
{
int i = -1, j = 0;
int t;
while (j != n) {
if (arr[j] % 2 == 0) {
i++;
// Swapping even and odd numbers
swap(arr[i], arr[j]);
}
j++;
}
// Printing segregated array
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 1, 3, 2, 4, 7, 6, 9, 10 };
int n = sizeof(arr) / sizeof(int);
arrayEvenAndOdd(arr, n);
return 0;
}
Java
// java code to segregate even odd
// numbers in an array
public class GFG {
// Function to segregate even
// odd numbers
static void arrayEvenAndOdd(
int arr[], int n)
{
int i = -1, j = 0;
while (j != n) {
if (arr[j] % 2 == 0)
{
i++;
// Swapping even and
// odd numbers
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
j++;
}
// Printing segregated array
for (int k = 0; k < n; k++)
System.out.print(arr[k] + " ");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 3, 2, 4, 7,
6, 9, 10 };
int n = arr.length;
arrayEvenAndOdd(arr, n);
}
}
// This code is contributed by Sam007
Python3
# Python3 code to segregate even odd # numbers in an array # Function to segregate even odd numbers def arrayEvenAndOdd(arr,n): i = -1 j= 0 while (j!=n): if (arr[j] % 2 ==0): i = i+1 # Swapping even and odd numbers arr[i],arr[j] = arr[j],arr[i] j = j+1 # Printing segregated array for i in arr: print (str(i) + " " ,end='') # Driver Code if __name__=='__main__': arr = [ 1 ,3, 2, 4, 7, 6, 9, 10] n = len(arr) arrayEvenAndOdd(arr,n) # This code was contributed by # Yatin Gupta
C#
// C# code to segregate even odd
// numbers in an array
using System;
class GFG {
// Function to segregate even
// odd numbers
static void arrayEvenAndOdd(
int []arr, int n)
{
int i = -1, j = 0;
while (j != n) {
if (arr[j] % 2 == 0)
{
i++;
// Swapping even and
// odd numbers
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
j++;
}
// Printing segregated array
for (int k = 0; k < n; k++)
Console.Write(arr[k] + " ");
}
// Driver code
static void Main()
{
int []arr = { 1, 3, 2, 4, 7,
6, 9, 10 };
int n = arr.Length;
arrayEvenAndOdd(arr, n);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP code to segregate even odd
// numbers in an array
// Function to segregate
// even odd numbers
function arrayEvenAndOdd($arr, $n)
{
$i = -1;
$j = 0;
$t;
while ($j != $n)
{
if ($arr[$j] % 2 == 0)
{
$i++;
// Swapping even and
// odd numbers
$x = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $x;
}
$j++;
}
// Printing segregated
// array
for ($i = 0; $i < $n; $i++)
echo $arr[$i] . " ";
}
// Driver code
$arr = array(1, 3, 2, 4, 7, 6, 9, 10);
$n = sizeof($arr);
arrayEvenAndOdd($arr, $n);
// This code is contributed by Anuj_67
?>
Javascript
<script>
// JavaScript code to segregate even odd
// numbers in an array
// Function to segregate even odd numbers
function arrayEvenAndOdd(arr, n)
{
let i = -1, j = 0;
let t;
while (j != n) {
if (arr[j] % 2 == 0) {
i++;
// Swapping even and odd numbers
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
j++;
}
// Printing segregated array
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver code
let arr = [ 1, 3, 2, 4, 7, 6, 9, 10 ];
let n = arr.length;
arrayEvenAndOdd(arr, n);
// This code is contributed by Surbhi Tyagi
</script>
Producción
2 4 6 10 7 1 9 3
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)