Dada una array de tamaño n que contiene el mismo número de números pares e impares. El problema es ordenar los números de tal manera que todos los números pares obtengan el índice par y los números impares obtengan el índice impar. El espacio auxiliar requerido es O(1).
Ejemplos:
Input : arr[] = {3, 6, 12, 1, 5, 8}
Output : 6 3 12 1 8 5
Input : arr[] = {10, 9, 7, 18, 13, 19, 4, 20, 21, 14}
Output : 10 9 18 7 20 19 4 13 14 21
Fuente: experiencia de entrevista de Amazon | Conjunto 410.
Acercarse :
- Comience desde la izquierda y mantenga dos índices, uno para posiciones pares y otro para posiciones impares.
- Atraviese estos índices desde la izquierda.
- En la posición par debe haber un número par y en las posiciones impares debe haber un número impar.
- Siempre que hay una discrepancia, intercambiamos los valores en el índice par e impar.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation to arrange
// odd and even numbers
#include <bits/stdc++.h>
using namespace std;
// function to arrange odd and even numbers
void arrangeOddAndEven(int arr[], int n)
{
int oddInd = 1;
int evenInd = 0;
while (true)
{
while (evenInd < n && arr[evenInd] % 2 == 0)
evenInd += 2;
while (oddInd < n && arr[oddInd] % 2 == 1)
oddInd += 2;
if (evenInd < n && oddInd < n)
swap (arr[evenInd], arr[oddInd]);
else
break;
}
}
// function to print the array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver program to test above
int main()
{
int arr[] = { 3, 6, 12, 1, 5, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original Array: ";
printArray(arr, n);
arrangeOddAndEven(arr, n);
cout << "\nModified Array: ";
printArray(arr, n);
return 0;
}
Java
// Java implementation to
// arrange odd and even numbers
import java.util.*;
import java.lang.*;
class GfG {
// function to arrange
// odd and even numbers
public static void arrangeOddAndEven(int arr[], int n)
{
int oddInd = 1;
int evenInd = 0;
while (true)
{
while (evenInd < n && arr[evenInd] % 2 == 0)
evenInd += 2;
while (oddInd < n && arr[oddInd] % 2 == 1)
oddInd += 2;
if (evenInd < n && oddInd < n)
{
int temp = arr[evenInd];
arr[evenInd] = arr[oddInd];
arr[oddInd] = temp;
}
else
break;
}
}
// function to print the array
public static void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver function
public static void main(String argc[]){
int arr[] = { 3, 6, 12, 1, 5, 8 };
int n = 6;
System.out.print("Original Array: ");
printArray(arr, n);
arrangeOddAndEven(arr, n);
System.out.print("\nModified Array: ");
printArray(arr, n);
}
}
// This code is contributed by Sagar Shukla
Python3
# Python3 implementation to
# arrange odd and even numbers
def arrangeOddAndEven(arr, n):
oddInd = 1
evenInd = 0
while (True):
while (evenInd < n and arr[evenInd] % 2 == 0):
evenInd += 2
while (oddInd < n and arr[oddInd] % 2 == 1):
oddInd += 2
if (evenInd < n and oddInd < n):
temp = arr[evenInd]
arr[evenInd] = arr[oddInd]
arr[oddInd] = temp;
else:
break
# function to print the array
def printArray(arr, n):
for i in range(0,n):
print(arr[i] , "",end="")
# Driver function
def main():
arr = [ 3, 6, 12, 1, 5, 8 ]
n = 6
print("Original Array: ",end="")
printArray(arr, n)
arrangeOddAndEven(arr, n)
print("\nModified Array: ",end="")
printArray(arr, n)
if __name__ == '__main__':
main()
# This code is contributed by 29AjayKumar
C#
// C# implementation to
// arrange odd and even numbers
using System;
class GFG {
// function to arrange
// odd and even numbers
public static void arrangeOddAndEven(int[] arr, int n)
{
int oddInd = 1;
int evenInd = 0;
while (true)
{
while (evenInd < n && arr[evenInd] % 2 == 0)
evenInd += 2;
while (oddInd < n && arr[oddInd] % 2 == 1)
oddInd += 2;
if (evenInd < n && oddInd < n)
{
int temp = arr[evenInd];
arr[evenInd] = arr[oddInd];
arr[oddInd] = temp;
}
else
break;
}
}
// function to print the array
public static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver function
public static void Main()
{
int[] arr = { 3, 6, 12, 1, 5, 8 };
int n = 6;
Console.Write("Original Array: ");
printArray(arr, n);
arrangeOddAndEven(arr, n);
Console.Write("\nModified Array: ");
printArray(arr, n);
}
}
// This code is contributed by Sam007
Javascript
<script>
// Javascript implementation to arrange
// odd and even numbers
// function to arrange odd and even numbers
function arrangeOddAndEven(arr, n)
{
let oddInd = 1;
let evenInd = 0;
while (true)
{
while (evenInd < n && arr[evenInd] % 2 == 0)
evenInd += 2;
while (oddInd < n && arr[oddInd] % 2 == 1)
oddInd += 2;
if (evenInd < n && oddInd < n)
{
let temp;
temp = arr[evenInd];
arr[evenInd] = arr[oddInd];
arr[oddInd] = temp;
}
else
break;
}
}
// function to print the array
function printArray(arr, n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver program to test above
let arr = [ 3, 6, 12, 1, 5, 8 ];
let n = arr.length;
document.write("Original Array: ");
printArray(arr, n);
arrangeOddAndEven(arr, n);
document.write("<br>" + "Modified Array: ");
printArray(arr, n);
// This code is contributed by Mayank Tyagi
</script>
Producción :
Original Array: 3 6 12 1 5 8 Modified Array: 6 3 12 1 8 5
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.
Este artículo es una contribución de Ayush Jauhari . 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