Dada una array, A de tamaño N que consta de los elementos 1 a N. Una array booleana B que consta de N-1 elementos indica que si B[i] es 1, entonces A[i] se puede intercambiar con A[i+1] .
Averigüe si A se puede ordenar intercambiando elementos.
Ejemplos:
Input : A[] = {1, 2, 5, 3, 4, 6}
B[] = {0, 1, 1, 1, 0}
Output : A can be sorted
We can swap A[2] with A[3] and then A[3] with A[4].
Input : A[] = {2, 3, 1, 4, 5, 6}
B[] = {0, 1, 1, 1, 1}
Output : A can not be sorted
We can not sort A by swapping elements as 1 can never be swapped with A[0]=2.
Aquí podemos intercambiar solo A[i] con A[i+1]. Entonces, para encontrar si la array se puede ordenar o no. Usando la array booleana B, podemos ordenar la array para una secuencia continua de 1 para B. Por último, podemos verificar si A está ordenada o no.
C++
// CPP program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
#include <bits/stdc++.h>
using namespace std;
// Return true if array can be
// sorted otherwise false
bool sortedAfterSwap(int A[], bool B[], int n)
{
int i, j;
// Check bool array B and sorts
// elements for continuous sequence of 1
for (i = 0; i < n - 1; i++) {
if (B[i]) {
j = i;
while (B[j])
j++;
// Sort array A from i to j
sort(A + i, A + 1 + j);
i = j;
}
}
// Check if array is sorted or not
for (i = 0; i < n; i++) {
if (A[i] != i + 1)
return false;
}
return true;
}
// Driver program to test sortedAfterSwap()
int main()
{
int A[] = { 1, 2, 5, 3, 4, 6 };
bool B[] = { 0, 1, 1, 1, 0 };
int n = sizeof(A) / sizeof(A[0]);
if (sortedAfterSwap(A, B, n))
cout << "A can be sorted\n";
else
cout << "A can not be sorted\n";
return 0;
}
Java
import java.util.Arrays;
// Java program to test whether an array
// can be sorted by swapping adjacent
// elements using boolean array
class GFG {
// Return true if array can be
// sorted otherwise false
static boolean sortedAfterSwap(int A[],
boolean B[], int n)
{
int i, j;
// Check bool array B and sorts
// elements for continuous sequence of 1
for (i = 0; i < n - 1; i++) {
if (B[i]) {
j = i;
while (B[j]) {
j++;
}
// Sort array A from i to j
Arrays.sort(A, i, 1 + j);
i = j;
}
}
// Check if array is sorted or not
for (i = 0; i < n; i++) {
if (A[i] != i + 1) {
return false;
}
}
return true;
}
// Driver program to test sortedAfterSwap()
public static void main(String[] args)
{
int A[] = { 1, 2, 5, 3, 4, 6 };
boolean B[] = { false, true, true, true, false };
int n = A.length;
if (sortedAfterSwap(A, B, n)) {
System.out.println("A can be sorted");
}
else {
System.out.println("A can not be sorted");
}
}
}
Python3
# Python 3 program to test whether an array
# can be sorted by swapping adjacent
# elements using a boolean array
# Return true if array can be
# sorted otherwise false
def sortedAfterSwap(A, B, n) :
# Check bool array B and sorts
# elements for continuous sequence of 1
for i in range(0, n - 1) :
if (B[i]== 1) :
j = i
while (B[j]== 1) :
j = j + 1
# Sort array A from i to j
A = A[0:i] + sorted(A[i:j + 1]) + A[j + 1:]
i = j
# Check if array is sorted or not
for i in range(0, n) :
if (A[i] != i + 1) :
return False
return True
# Driver program to test sortedAfterSwap()
A = [ 1, 2, 5, 3, 4, 6 ]
B = [ 0, 1, 1, 1, 0 ]
n = len(A)
if (sortedAfterSwap(A, B, n)) :
print("A can be sorted")
else :
print("A can not be sorted")
# This code is contributed
# by Nikita Tiwari.
C#
// C# program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
using System;
class GFG {
// Return true if array can be
// sorted otherwise false
static bool sortedAfterSwap(int[] A,
bool[] B,
int n)
{
int i, j;
// Check bool array B and sorts
// elements for continuous sequence of 1
for (i = 0; i < n - 1; i++) {
if (B[i]) {
j = i;
while (B[j]) {
j++;
}
// Sort array A from i to j
Array.Sort(A, i, 1 + j);
i = j;
}
}
// Check if array is sorted or not
for (i = 0; i < n; i++) {
if (A[i] != i + 1) {
return false;
}
}
return true;
}
// Driver Code
public static void Main()
{
int[] A = { 1, 2, 5, 3, 4, 6 };
bool[] B = { false, true, true, true, false };
int n = A.Length;
if (sortedAfterSwap(A, B, n)) {
Console.WriteLine("A can be sorted");
}
else {
Console.WriteLine("A can not be sorted");
}
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
// Return true if array can be
// sorted otherwise false
function sortedAfterSwap($A, $B, $n)
{
// Check bool array B and sorts
// elements for continuous sequence of 1
for ($i = 0; $i < $n - 1; $i++)
{
if ($B[$i])
{
$j = $i;
while ($B[$j])
$j++;
// Sort array A from i to j
sort($A);
$i = $j;
}
}
// Check if array is sorted or not
for ($i = 0; $i < $n; $i++)
{
if ($A[$i] != $i + 1)
return false;
}
return true;
}
// Driver Code
$A = array(1, 2, 5, 3, 4, 6);
$B = array(0, 1, 1, 1, 0);
$n = count($A);
if (sortedAfterSwap($A, $B, $n))
echo "A can be sorted\n";
else
echo "A can not be sorted\n";
// This code is contributed by Sam007
?>
Javascript
<script>
// JavaScript program to test whether an array
// can be sorted by swapping adjacent
// elements using boolean array
// Return true if array can be
// sorted otherwise false
function sortedAfterSwap(A, B, n)
{
let i, j;
// Check bool array B and sorts
// elements for continuous sequence of 1
for (i = 0; i < n - 1; i++) {
if (B[i]) {
j = i;
while (B[j]) {
j++;
}
// Sort array A from i to j
A.sort();
i = j;
}
}
// Check if array is sorted or not
for (i = 0; i < n; i++) {
if (A[i] != i + 1) {
return false;
}
}
return true;
}
// Driver Code
let A = [ 1, 2, 5, 3, 4, 6 ];
let B = [ false, true, true, true, false ];
let n = A.length;
if (sortedAfterSwap(A, B, n)) {
document.write("A can be sorted");
}
else {
document.write("A can not be sorted");
}
// This code is contributed by code_hunt.
</script>
Producción:
A can be sorted
Complejidad de tiempo: O(n*n*logn), donde n time se usa para iterar y n*logn para ordenar dentro de la array
Espacio auxiliar: O(1), ya que no se requiere espacio adicional
Enfoque alternativo
Aquí discutimos un enfoque muy intuitivo que también da la respuesta en tiempo O(n) para todos los casos. La idea aquí es que siempre que la array binaria tenga 1, verifiquemos si ese índice en la array A tiene i+1 o no. Si no contiene i+1, simplemente intercambiamos a[i] con a[i+1].
La razón de esto es que la array debe tener i+1 almacenado en el índice i. Y si la array se puede ordenar, entonces la única operación permitida es el intercambio. Por lo tanto, si la condición requerida no se cumple, simplemente intercambiamos. Si la array se puede ordenar, el intercambio nos acercará un paso más a la respuesta correcta. Y como era de esperar, si la array no se puede ordenar, el intercambio conduciría a otra versión sin ordenar de la misma array.
C++
// CPP program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
#include <bits/stdc++.h>
using namespace std;
// Return true if array can be
// sorted otherwise false
bool sortedAfterSwap(int A[], bool B[], int n)
{
for (int i = 0; i < n - 1; i++) {
if (B[i]) {
if (A[i] != i + 1)
swap(A[i], A[i + 1]);
}
}
// Check if array is sorted or not
for (int i = 0; i < n; i++) {
if (A[i] != i + 1)
return false;
}
return true;
}
// Driver program to test sortedAfterSwap()
int main()
{
int A[] = { 1, 2, 5, 3, 4, 6 };
bool B[] = { 0, 1, 1, 1, 0 };
int n = sizeof(A) / sizeof(A[0]);
if (sortedAfterSwap(A, B, n))
cout << "A can be sorted\n";
else
cout << "A can not be sorted\n";
return 0;
}
Java
// Java program to test whether an array
// can be sorted by swapping adjacent
// elements using boolean array
class GFG
{
// Return true if array can be
// sorted otherwise false
static int sortedAfterSwap(int[] A,
int[] B, int n)
{
int t = 0;
for (int i = 0; i < n - 1; i++)
{
if (B[i] != 0)
{
if (A[i] != i + 1)
t = A[i];
A[i] = A[i + 1];
A[i + 1] = t;
}
}
// Check if array is sorted or not
for (int i = 0; i < n; i++)
{
if (A[i] != i + 1)
return 0;
}
return 1;
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 1, 2, 5, 3, 4, 6 };
int[] B = { 0, 1, 1, 1, 0 };
int n = A.length;
if (sortedAfterSwap(A, B, n) == 0)
System.out.println("A can be sorted");
else
System.out.println("A can not be sorted");
}
}
// This code is contributed
// by Mukul Singh.
Python3
# Python3 program to test whether array
# can be sorted by swapping adjacent
# elements using boolean array
# Return true if array can be
# sorted otherwise false
def sortedAfterSwap(A,B,n):
for i in range(0,n-1):
if B[i]:
if A[i]!=i+1:
A[i], A[i+1] = A[i+1], A[i]
# Check if array is sorted or not
for i in range(n):
if A[i]!=i+1:
return False
return True
# Driver program
if __name__=='__main__':
A = [1, 2, 5, 3, 4, 6]
B = [0, 1, 1, 1, 0]
n =len(A)
if (sortedAfterSwap(A, B, n)) :
print("A can be sorted")
else :
print("A can not be sorted")
# This code is contributed by
# Shrikant13
C#
// C# program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
using System;
class GFG
{
// Return true if array can be
// sorted otherwise false
static int sortedAfterSwap(int[] A,
int[] B, int n)
{
int t = 0;
for (int i = 0; i < n - 1; i++)
{
if (B[i] != 0)
{
if (A[i] != i + 1)
t = A[i];
A[i] = A[i + 1];
A[i + 1] = t;
}
}
// Check if array is sorted or not
for (int i = 0; i < n; i++)
{
if (A[i] != i + 1)
return 0;
}
return 1;
}
// Driver Code
public static void Main()
{
int[] A = { 1, 2, 5, 3, 4, 6 };
int[] B = { 0, 1, 1, 1, 0 };
int n = A.Length;
if (sortedAfterSwap(A, B, n) == 0)
Console.WriteLine("A can be sorted");
else
Console.WriteLine("A can not be sorted");
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP program to test whether array
// can be sorted by swapping adjacent
// elements using boolean array
// Return true if array can be
// sorted otherwise false
function sortedAfterSwap(&$A, &$B, $n)
{
for ($i = 0; $i < $n - 1; $i++)
{
if ($B[$i])
{
if ($A[$i] != $i + 1)
{
$t = $A[$i];
$A[$i] = $A[$i + 1];
$A[$i + 1] = $t;
}
}
}
// Check if array is sorted or not
for ($i = 0; $i < $n; $i++)
{
if ($A[$i] != $i + 1)
return false;
}
return true;
}
// Driver Code
$A = array( 1, 2, 5, 3, 4, 6 );
$B = array( 0, 1, 1, 1, 0 );
$n = sizeof($A);
if (sortedAfterSwap($A, $B, $n))
echo "A can be sorted\n";
else
echo "A can not be sorted\n";
// This code is contributed by ita_c
?>
Javascript
<script>
// JavaScript program to test whether an array
// can be sorted by swapping adjacent
// elements using boolean array
// Return true if array can be
// sorted otherwise false
function sortedAfterSwap(A,B,n)
{
let t = 0;
for (let i = 0; i < n - 1; i++)
{
if (B[i] != 0)
{
if (A[i] != i + 1)
t = A[i];
A[i] = A[i + 1];
A[i + 1] = t;
}
}
// Check if array is sorted or not
for (let i = 0; i < n; i++)
{
if (A[i] != i + 1)
return 0;
}
return 1;
}
// Driver Code
let A = [ 1, 2, 5, 3, 4, 6 ];
let B = [ 0, 1, 1, 1, 0 ];
let n = A.length;
if (sortedAfterSwap(A, B, n) == 0)
document.write("A can be sorted");
else
document.write("A can not be sorted");
// This code is contributed
// by sravan kumar Gottumukkala
</script>
Producción
A can be sorted
Complejidad temporal: O(n)
Espacio auxiliar: O(1)