Dada una array que contiene N elementos. Averigüe si es posible clasificarlo en orden no decreciente usando al menos un intercambio.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: SÍ
La array ya está ordenada
Entrada: arr[] = {3, 2, 1}
Salida: SÍ
Intercambie 3 y 1 para obtener [1, 2, 3]
Entrada: arr[] = {4, 1, 2, 3}
Salida: NO
Un enfoque simple es ordenar la array y comparar la posición requerida del elemento y la posición actual del elemento. Si no hay discrepancias, la array ya está ordenada. Si hay exactamente 2 discrepancias, podemos intercambiar los términos que no están en la posición para obtener la array ordenada.
C++
// CPP program to check if an array can be sorted
// with at-most one swap
#include <bits/stdc++.h>
using namespace std;
bool checkSorted(int n, int arr[])
{
// Create a sorted copy of original array
int b[n];
for (int i = 0; i < n; i++)
b[i] = arr[i];
sort(b, b + n);
// Check if 0 or 1 swap required to
// get the sorted array
int ct = 0;
for (int i = 0; i < n; i++)
if (arr[i] != b[i])
ct++;
if (ct == 0 || ct == 2)
return true;
else
return false;
}
// Driver Program to test above function
int main()
{
int arr[] = {1, 5, 3, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);
if (checkSorted(n, arr))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to check if an array
// can be sorted with at-most one swap
import java.util.Arrays;
class GFG
{
static boolean checkSorted(int n, int arr[])
{
// Create a sorted copy of original array
int []b = new int[n];
for (int i = 0; i < n; i++)
b[i] = arr[i];
Arrays.sort(b, 0, n);
// Check if 0 or 1 swap required to
// get the sorted array
int ct = 0;
for (int i = 0; i < n; i++)
if (arr[i] != b[i])
ct++;
if (ct == 0 || ct == 2)
return true;
else
return false;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {1, 5, 3, 4, 2};
int n = arr.length;
if (checkSorted(n, arr))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by 29AjayKumar
Python 3
# A linear Python 3 program to check
# if array becomes sorted after one swap
def checkSorted(n, arr):
# Create a sorted copy of
# original array
b = []
for i in range(n):
b.append(arr[i])
b.sort()
# Check if 0 or 1 swap required
# to get the sorted array
ct = 0
for i in range(n):
if arr[i] != b[i]:
ct += 1
if ct == 0 or ct == 2:
return True
else:
return False
# Driver Code
if __name__ == '__main__':
arr = [1, 5, 3, 4, 2]
n = len(arr)
if checkSorted(n, arr):
print("Yes")
else:
print("No")
# This code is contributed
# by Rituraj Jain
C#
// C# program to check if an array
// can be sorted with at-most one swap
using System;
class GFG
{
static Boolean checkSorted(int n, int []arr)
{
// Create a sorted copy of original array
int []b = new int[n];
for (int i = 0; i < n; i++)
b[i] = arr[i];
Array.Sort(b, 0, n);
// Check if 0 or 1 swap required to
// get the sorted array
int ct = 0;
for (int i = 0; i < n; i++)
if (arr[i] != b[i])
ct++;
if (ct == 0 || ct == 2)
return true;
else
return false;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1, 5, 3, 4, 2};
int n = arr.Length;
if (checkSorted(n, arr))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to check if an array can be sorted
// with at-most one swap
function checkSorted(n, arr)
{
// Create a sorted copy of original array
var b = Array(n).fill(0);
for (var i = 0; i < n; i++)
b[i] = arr[i];
b.sort();
// Check if 0 or 1 swap required to
// get the sorted array
var ct = 0;
for (var i = 0; i < n; i++)
if (arr[i] != b[i])
ct++;
if (ct == 0 || ct == 2)
return true;
else
return false;
}
// Driver Program to test above function
var arr = [ 1, 5, 3, 4, 2 ];
var n = arr.length;
if (checkSorted(n, arr))
document.write( "Yes");
else
document.write("No");
// This code is contributed by noob2000.
</script>
Producción:
Yes
Complejidad de tiempo: O(n Log n)
Una solución eficiente es verificar en tiempo lineal. Consideremos diferentes casos que pueden aparecer después de un intercambio.
- Intercambiamos elementos adyacentes. Por ejemplo {1, 2, 3, 4 , 5} se convierte en {1, 2, 4, 3, 5}
- Intercambiamos elementos no adyacentes. Por ejemplo, {1, 2 , 3, 4, 5 } se convierte en {1, 5, 3, 4, 2}
Recorremos la array dada. Para cada elemento, verificamos si es más pequeño que el elemento anterior. Contamos tales ocurrencias. Si el recuento de tales ocurrencias es más de 2, entonces no podemos ordenar la array con un intercambio. Si el conteo es uno, podemos encontrar elementos para intercambiar (menor y anterior).
Si la cuenta es dos, podemos encontrar elementos para intercambiar (antes del primero más pequeño y el segundo más pequeño).
Después del intercambio, verificamos nuevamente si la array se ordena o no. Verificamos esto para manejar casos como {4, 1, 2, 3}
C++
// A linear CPP program to check if array becomes
// sorted after one swap
#include <bits/stdc++.h>
using namespace std;
int checkSorted(int n, int arr[])
{
// Find counts and positions of
// elements that are out of order.
int first = 0, second = 0;
int count = 0;
for (int i = 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
count++;
if (first == 0)
first = i;
else
second = i;
}
}
// If there are more than two elements
// are out of order.
if (count > 2)
return false;
// If all elements are sorted already
if (count == 0)
return true;
// Cases like {1, 5, 3, 4, 2}
// We swap 5 and 2.
if (count == 2)
swap(arr[first - 1], arr[second]);
// Cases like {1, 2, 4, 3, 5}
else if (count == 1)
swap(arr[first - 1], arr[first]);
// Now check if array becomes sorted
// for cases like {4, 1, 2, 3}
for (int i = 1; i < n; i++)
if (arr[i] < arr[i - 1])
return false;
return true;
}
// Driver Program to test above function
int main()
{
int arr[] = { 1, 4, 3, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
if (checkSorted(n, arr))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// A linear Java program to check if
// array becomes sorted after one swap
class GFG
{
static boolean checkSorted(int n, int arr[])
{
// Find counts and positions of
// elements that are out of order.
int first = 0, second = 0;
int count = 0;
for (int i = 1; i < n; i++)
{
if (arr[i] < arr[i - 1])
{
count++;
if (first == 0)
first = i;
else
second = i;
}
}
// If there are more than two elements
// are out of order.
if (count > 2)
return false;
// If all elements are sorted already
if (count == 0)
return true;
// Cases like {1, 5, 3, 4, 2}
// We swap 5 and 2.
if (count == 2)
swap(arr, first - 1, second);
// Cases like {1, 2, 4, 3, 5}
else if (count == 1)
swap(arr, first - 1, first);
// Now check if array becomes sorted
// for cases like {4, 1, 2, 3}
for (int i = 1; i < n; i++)
if (arr[i] < arr[i - 1])
return false;
return true;
}
static int[] swap(int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 4, 3, 2 };
int n = arr.length;
if (checkSorted(n, arr))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Rajput-Ji
Python 3
# A linear Python 3 program to check
# if array becomes sorted after one swap
def checkSorted(n, arr):
# Find counts and positions of
# elements that are out of order.
first, second = 0, 0
count = 0
for i in range(1, n):
if arr[i] < arr[i - 1]:
count += 1
if first == 0:
first = i
else:
second = i
# If there are more than two elements
# which are out of order.
if count > 2:
return False
# If all elements are sorted already
if count == 0:
return True
# Cases like {1, 5, 3, 4, 2}
# We swap 5 and 2.
if count == 2:
(arr[first - 1],
arr[second]) = (arr[second],
arr[first - 1])
# Cases like {1, 2, 4, 3, 5}
elif count == 1:
(arr[first - 1],
arr[first]) = (arr[first],
arr[first - 1])
# Now check if array becomes sorted
# for cases like {4, 1, 2, 3}
for i in range(1, n):
if arr[i] < arr[i - 1]:
return False
return True
# Driver Code
if __name__ == '__main__':
arr = [1, 4, 3, 2]
n = len(arr)
if checkSorted(n, arr):
print("Yes")
else:
print("No")
# This code is contributed
# by Rituraj Jain
C#
// A linear C# program to check if
// array becomes sorted after one swap
using System;
class GFG
{
static bool checkSorted(int n, int []arr)
{
// Find counts and positions of
// elements that are out of order.
int first = 0, second = 0;
int count = 0;
for (int i = 1; i < n; i++)
{
if (arr[i] < arr[i - 1])
{
count++;
if (first == 0)
first = i;
else
second = i;
}
}
// If there are more than two elements
// are out of order.
if (count > 2)
return false;
// If all elements are sorted already
if (count == 0)
return true;
// Cases like {1, 5, 3, 4, 2}
// We swap 5 and 2.
if (count == 2)
swap(arr, first - 1, second);
// Cases like {1, 2, 4, 3, 5}
else if (count == 1)
swap(arr, first - 1, first);
// Now check if array becomes sorted
// for cases like {4, 1, 2, 3}
for (int i = 1; i < n; i++)
if (arr[i] < arr[i - 1])
return false;
return true;
}
static int[] swap(int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 4, 3, 2 };
int n = arr.Length;
if (checkSorted(n, arr))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// A linear Javascript program to check if array becomes
// sorted after one swap
function checkSorted(n, arr)
{
// Find counts and positions of
// elements that are out of order.
var first = 0, second = 0;
var count = 0;
for (var i = 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
count++;
if (first == 0)
first = i;
else
second = i;
}
}
// If there are more than two elements
// are out of order.
if (count > 2)
return false;
// If all elements are sorted already
if (count == 0)
return true;
// Cases like {1, 5, 3, 4, 2}
// We swap 5 and 2.
if (count == 2)
[arr[first - 1], arr[second]] = [arr[second], arr[first - 1]];
// Cases like {1, 2, 4, 3, 5}
else if (count == 1)
[arr[first - 1], arr[first]] = [arr[first], arr[first - 1]];
// Now check if array becomes sorted
// for cases like {4, 1, 2, 3}
for (var i = 1; i < n; i++)
if (arr[i] < arr[i - 1])
return false;
return true;
}
// Driver Program to test above function
var arr = [1, 4, 3, 2];
var n = arr.length;
if (checkSorted(n, arr))
document.write( "Yes");
else
document.write( "No");
// This code is contributed by famously.
</script>
Producción:
Yes
Complejidad de tiempo: O(n)
Ejercicio: ¿Cómo verificar si una array se puede ordenar con dos intercambios?
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA