Dada una array binaria, la tarea es ordenar esta array binaria utilizando intercambios mínimos. Solo podemos intercambiar elementos adyacentes
Ejemplos:
Input : [0, 0, 1, 0, 1, 0, 1, 1] Output : 3 1st swap : [0, 0, 1, 0, 0, 1, 1, 1] 2nd swap : [0, 0, 0, 1, 0, 1, 1, 1] 3rd swap : [0, 0, 0, 0, 1, 1, 1, 1] Input : Array = [0, 1, 0, 1, 0] Output : 3
Enfoque:
Esto se puede hacer encontrando el número de ceros a la derecha de cada 1 y agregándolos. Para ordenar la array, cada uno siempre tiene que realizar una operación de intercambio con cada cero en su lado derecho. Entonces, el número total de operaciones de intercambio para un 1 en particular en la array es el número de ceros en su lado derecho. Encuentre el número de ceros en el lado derecho para cada uno, es decir, el número de intercambios y súmelos todos para obtener el número total de intercambios.
Implementación:
C++
// C++ code to find minimum number of
// swaps to sort a binary array
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum swaps to
// sort an array of 0s and 1s.
int findMinSwaps(int arr[], int n)
{
// Array to store count of zeroes
int noOfZeroes[n];
memset(noOfZeroes, 0, sizeof(noOfZeroes));
int i, count = 0;
// Count number of zeroes
// on right side of every one.
noOfZeroes[n - 1] = 1 - arr[n - 1];
for (i = n - 2; i >= 0; i--) {
noOfZeroes[i] = noOfZeroes[i + 1];
if (arr[i] == 0)
noOfZeroes[i]++;
}
// Count total number of swaps by adding number
// of zeroes on right side of every one.
for (i = 0; i < n; i++) {
if (arr[i] == 1)
count += noOfZeroes[i];
}
return count;
}
// Driver code
int main()
{
int arr[] = { 0, 0, 1, 0, 1, 0, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMinSwaps(arr, n);
return 0;
}
Java
// Java code to find minimum number of
// swaps to sort a binary array
class gfg {
static int findMinSwaps(int arr[], int n)
{
// Array to store count of zeroes
int noOfZeroes[] = new int[n];
int i, count = 0;
// Count number of zeroes
// on right side of every one.
noOfZeroes[n - 1] = 1 - arr[n - 1];
for (i = n - 2; i >= 0; i--)
{
noOfZeroes[i] = noOfZeroes[i + 1];
if (arr[i] == 0)
noOfZeroes[i]++;
}
// Count total number of swaps by adding number
// of zeroes on right side of every one.
for (i = 0; i < n; i++)
{
if (arr[i] == 1)
count += noOfZeroes[i];
}
return count;
}
// Driver Code
public static void main(String args[])
{
int ar[] = { 0, 0, 1, 0, 1, 0, 1, 1 };
System.out.println(findMinSwaps(ar, ar.length));
}
}
// This code is contributed by Niraj_Pandey.
Python3
# Python3 code to find minimum number of # swaps to sort a binary array # Function to find minimum swaps to # sort an array of 0s and 1s. def findMinSwaps(arr, n) : # Array to store count of zeroes noOfZeroes = [0] * n count = 0 # Count number of zeroes # on right side of every one. noOfZeroes[n - 1] = 1 - arr[n - 1] for i in range(n-2, -1, -1) : noOfZeroes[i] = noOfZeroes[i + 1] if (arr[i] == 0) : noOfZeroes[i] = noOfZeroes[i] + 1 # Count total number of swaps by adding # number of zeroes on right side of # every one. for i in range(0, n) : if (arr[i] == 1) : count = count + noOfZeroes[i] return count # Driver code arr = [ 0, 0, 1, 0, 1, 0, 1, 1 ] n = len(arr) print (findMinSwaps(arr, n)) # This code is contributed by Manish Shaw # (manishshaw1)
C#
// C# code to find minimum number of
// swaps to sort a binary array
using System;
class GFG {
static int findMinSwaps(int []arr, int n)
{
// Array to store count of zeroes
int []noOfZeroes = new int[n];
int i, count = 0;
// Count number of zeroes
// on right side of every one.
noOfZeroes[n - 1] = 1 - arr[n - 1];
for (i = n - 2; i >= 0; i--)
{
noOfZeroes[i] = noOfZeroes[i + 1];
if (arr[i] == 0)
noOfZeroes[i]++;
}
// Count total number of swaps by
// adding number of zeroes on right
// side of every one.
for (i = 0; i < n; i++)
{
if (arr[i] == 1)
count += noOfZeroes[i];
}
return count;
}
// Driver Code
public static void Main()
{
int []ar = { 0, 0, 1, 0, 1,
0, 1, 1 };
Console.WriteLine(
findMinSwaps(ar, ar.Length));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP code to find minimum number of
// swaps to sort a binary array
// Function to find minimum swaps to
// sort an array of 0s and 1s.
function findMinSwaps($arr, $n)
{
// Array to store count of zeroes
$noOfZeroes[$n] = array();
$noOfZeroes = array_fill(0, $n, true);
$count = 0;
// Count number of zeroes
// on right side of every one.
$noOfZeroes[$n - 1] = 1 - $arr[$n - 1];
for ($i = $n - 2; $i >= 0; $i--)
{
$noOfZeroes[$i] = $noOfZeroes[$i + 1];
if ($arr[$i] == 0)
$noOfZeroes[$i]++;
}
// Count total number of swaps by adding
// number of zeroes on right side of every one.
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] == 1)
$count += $noOfZeroes[$i];
}
return $count;
}
// Driver code
$arr = array( 0, 0, 1, 0, 1, 0, 1, 1 );
$n = sizeof($arr);
echo findMinSwaps($arr, $n);
// This code is contributed by Sach_code
?>
Javascript
<script>
// JavaScript program to find minimum number of
// swaps to sort a binary array
function findMinSwaps(arr, n)
{
// Array to store count of zeroes
let noOfZeroes = [];
let i, count = 0;
// Count number of zeroes
// on right side of every one.
noOfZeroes[n - 1] = 1 - arr[n - 1];
for (i = n - 2; i >= 0; i--)
{
noOfZeroes[i] = noOfZeroes[i + 1];
if (arr[i] == 0)
noOfZeroes[i]++;
}
// Count total number of swaps by adding number
// of zeroes on right side of every one.
for (i = 0; i < n; i++)
{
if (arr[i] == 1)
count += noOfZeroes[i];
}
return count;
}
// Driver Code
let ar = [ 0, 0, 1, 0, 1, 0, 1, 1 ];
document.write(findMinSwaps(ar, ar.length));
// This code is contributed by avijitmondal1998.
</script>
Producción
3
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Solución optimizada
de espacio: no se necesita un espacio auxiliar. Solo necesitamos comenzar a leer la lista desde atrás y realizar un seguimiento de la cantidad de ceros que encontramos. Si encontramos un 1, la cantidad de ceros es la cantidad de intercambios necesarios para colocar el 1 en el lugar correcto.
C++
#include <iostream>
using namespace std;
int minswaps(int arr[], int n)
{
int count = 0;
int num_unplaced_zeros = 0;
for(int index=n-1;index>=0;index--)
{
if(arr[index] == 0)
num_unplaced_zeros += 1;
else
count += num_unplaced_zeros;
}
return count;
}
// Driver Code
int main()
{
int arr[] = {0, 0, 1, 0, 1, 0, 1, 1};
cout<<minswaps(arr, 9);
return 0;
}
// this code is contributed by Manu Pathria
Java
import java.io.*;
class GFG {
public static int minswaps(int arr[], int n)
{
int count = 0;
int num_unplaced_zeros = 0;
for (int index = n - 1; index >= 0; index--)
{
if (arr[index] == 0)
num_unplaced_zeros += 1;
else
count += num_unplaced_zeros;
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 0, 0, 1, 0, 1, 0, 1, 1 };
System.out.println(minswaps(arr, 9));
}
}
// this code is contributed by Manu Pathria
Python3
def minswaps(arr): count = 0 num_unplaced_zeros = 0 for index in range(len(arr)-1, -1, -1): if arr[index] == 0: num_unplaced_zeros += 1 else: count += num_unplaced_zeros return count arr = [0, 0, 1, 0, 1, 0, 1, 1] print(minswaps(arr))
C#
using System;
class GFG {
static int minswaps(int[] arr, int n)
{
int count = 0;
int num_unplaced_zeros = 0;
for (int index = n - 2; index >= 0; index--)
{
if (arr[index] == 0)
num_unplaced_zeros += 1;
else
count += num_unplaced_zeros;
}
return count;
}
static void Main() {
int[] arr = { 0, 0, 1, 0, 1, 0, 1, 1 };
Console.WriteLine(minswaps(arr, 9));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
function minswaps(arr, n)
{
var count = 0;
var num_unplaced_zeros = 0;
for(var index = n - 1; index >= 0; index--)
{
if(arr[index] == 0)
num_unplaced_zeros += 1;
else
count += num_unplaced_zeros;
}
return count;
}
// Driver Code
var arr = [0, 0, 1, 0, 1, 0, 1, 1];
document.write( minswaps(arr, 9));
// This code is contributed by itsok.
</script>
Producción
3
Complejidad temporal: O(n)
Espacio auxiliar: O(1)