Dada una array de 0 y 1 en orden aleatorio. Separe los 0 en el lado izquierdo y los 1 en el lado derecho de la array. Atraviesa la array solo una vez.
Ejemplos:
Input : arr[] = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] Output : arr[] = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] Input : arr[] = [1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1] Output : arr[] = [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
Ya hemos discutido una solución Separar 0s y 1s en una array
En esta publicación, se discute una nueva solución.
Paso 1: aquí podemos tomar dos punteros tipo 0 (para el elemento 0) comenzando desde el principio (índice = 0) y tipo 1 (para el elemento 1) comenzando desde el índice final.
Paso 2: Tenemos la intención de poner 1 en el lado derecho de la array. Una vez que hayamos hecho esto, 0 definitivamente estará hacia el lado izquierdo de la array para lograr esto, hacemos lo siguiente.
Comparamos elementos en el tipo de índice 0
1) si este es 1, entonces debe moverse hacia el lado derecho, por lo que debemos intercambiarlo con el tipo de índice 1, una vez intercambiados, estamos seguros de que el elemento en el tipo de índice 1 es ‘1’, por lo que debemos disminuir el tipo de índice 1
2) de lo contrario, será 0, entonces necesitamos incrementar de forma simple el tipo de índice 0
C++14
// CPP program to sort an array with two types
// of values in one traversal.
#include <bits/stdc++.h>
using namespace std;
/* Method for segregation 0 and 1 given
input array */
void segregate0and1(int arr[], int n)
{
int type0 = 0;
int type1 = n - 1;
while (type0 < type1) {
if (arr[type0] == 1) {
swap(arr[type0], arr[type1]);
type1--;
}
else {
type0++;
}
}
}
// Driver program
int main()
{
int arr[] = { 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1 };
int n = sizeof(arr)/sizeof(arr[0]);
segregate0and1(arr, n);
for (int a : arr)
cout << a << " ";
}
Java
// Java program to sort an array with two types
// of values in one traversal.public class GFG {
/* Method for segregation 0 and 1
given input array */
class segregation {
static void segregate0and1(int arr[], int n)
{
int type0 = 0;
int type1 = n - 1;
while (type0 < type1) {
if (arr[type0] == 1) {
// swap type0 and type1
arr[type0] = arr[type0] + arr[type1];
arr[type1] = arr[type0] - arr[type1];
arr[type0] = arr[type0] - arr[type1];
type1--;
}
else {
type0++;
}
}
}
// Driver program
public static void main(String[] args)
{
int arr[]
= { 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0 };
segregate0and1(arr, arr.length);
for (int a : arr)
System.out.print(a + " ");
}
}
Python3
# Python3 program to sort an array with # two types of values in one traversal. # Method for segregation 0 and # 1 given input array def segregate0and1(arr, n): type0 = 0; type1 = n - 1 while (type0 < type1): if (arr[type0] == 1): arr[type0], arr[type1] = arr[type1], arr[type0] type1 -= 1 else: type0 += 1 # Driver Code arr = [1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1] n = len(arr) segregate0and1(arr, n) for i in range(0, n): print(arr[i], end = " ") # This code is contributed by Smitha Dinesh Semwal
C#
// C# program to sort an array with two types
// of values in one traversal.
using System;
class GFG {
static void segregate0and1(int []arr, int n)
{
int type0 = 0;
int type1 = n - 1;
while (type0 < type1)
{
if (arr[type0] == 1)
{
// swap type0 and type1
arr[type0] = arr[type0] + arr[type1];
arr[type1] = arr[type0]-arr[type1];
arr[type0] = arr[type0]-arr[type1];
type1--;
}
else {
type0++;
}
}
}
// Driver program
public static void Main()
{
int []arr = { 1, 1, 1, 0, 1, 0, 0,
1, 1, 1, 1 };
segregate0and1(arr, arr.Length);
for (int i = 0; i < arr.Length; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to sort an array with two
// types of values in one traversal.
/* Method for segregation 0 and 1
given input array */
function segregate0and1($arr, $n)
{
$type0 = 0;
$type1 = $n - 1;
while ($type0 < $type1)
{
if ($arr[$type0] == 1)
{
$temp = $arr[$type0];
$arr[$type0] = $arr[$type1];
$arr[$type1] = $temp;
$type1--;
}
else
{
$type0++;
}
}
return $arr;
}
// Driver Code
$arr = array( 1, 1, 1, 0, 1, 0,
0, 1, 1, 1, 1 );
$n = count($arr);
$arr1 = segregate0and1($arr, $n);
for($i = 0; $i < $n ; $i++ )
echo $arr1[$i] . " ";
// This code is contributed by Rajput-Ji
?>
Javascript
<script>
// JavaScript program to sort an array with two types
// of values in one traversal.
function segregate0and1(arr, n)
{
let type0 = 0;
let type1 = n - 1;
while (type0 < type1)
{
if (arr[type0] == 1)
{
// swap type0 and type1
arr[type0] = arr[type0] + arr[type1];
arr[type1] = arr[type0]-arr[type1];
arr[type0] = arr[type0]-arr[type1];
type1--;
}
else {
type0++;
}
}
}
// Driver Code
let arr = [1, 1, 1, 0, 1, 0, 0,
1, 1, 1, 1 ];
segregate0and1(arr, arr.length);
for (let i = 0; i < arr.length; i++)
document.write(arr[i] + " ");
// This code is contributed by avijitmondal1998.
</script>
0 0 0 1 1 1 1 1 1 1 1
Complejidad de tiempo : O(n)
Espacio Auxiliar: O(1)