Dada una array de tamaño N, la tarea es determinar si es posible ordenar la array o no con solo una mezcla. En una mezcla, podemos mover algunos elementos contiguos desde el final de la array y colocarlos al frente de la array.
Por ejemplo:
- A = {2, 3, 1, 2}, podemos desplazar {1, 2} desde el final del arreglo al frente del arreglo para ordenarlo.
- A = {1, 2, 3, 2} ya que no podemos ordenarlo de una sola vez, por lo tanto, no es posible ordenar la array.
Ejemplos:
Input: arr[] = {1, 2, 3, 4}
Output: Possible
Since this array is already sorted hence no need for shuffle.
Input: arr[] = {6, 8, 1, 2, 5}
Output: Possible
Place last three elements at the front
in the same order i.e. {1, 2, 5, 6, 8}
Acercarse:
- Compruebe si la array ya está ordenada o no. Si es así, devuelve verdadero.
- De lo contrario, comience a recorrer los elementos de la array hasta que el elemento actual sea más pequeño que el siguiente. Almacene ese índice donde arr[i] > arr[i+1].
- Recorra desde ese punto y verifique si los elementos de ese índice están en orden creciente o no.
- Si se cumplen las dos condiciones anteriores, compruebe si el último elemento es menor o igual que el primer elemento de la array dada.
- Escriba «Posible» si se cumplen las tres condiciones anteriores; de lo contrario, escriba «No es posible» si falla alguna de las 3 condiciones anteriores.
A continuación se muestra la implementación del enfoque anterior:
PHP
<?php
// PHP implementation of
// above approach
// Function to check if
// it is possible
function is_sorted($a, $n)
{
$c1 = 0; $c2 = 0;
// if array is ascending
for($i = 0; $i < $n - 1; $i++)
{
if($a[$i] <= $a[$i + 1])
$c1++;
}
// if array is descending
for($i = 1; $i < $n; $i++)
{
if($a[$i] <= $a[$i - 1])
$c2++;
}
if($c1 == $n || $c2 == $n)
return true;
return false;
}
function isPossible($a, $n)
{
// step 1
if (is_sorted($a, $n))
{
echo "Possible" . "
";
}
else
{
// break where a[i] > a[i+1]
$flag = true;
$i;
for ($i = 0; $i < $n - 1; $i++)
{
if ($a[$i] > $a[$i + 1])
{
break;
}
}
// break point + 1
$i++;
// check whether the sequence is
// further increasing or not
for ($k = $i; $k < $n - 1; $k++)
{
if ($a[$k] > $a[$k + 1])
{
$flag = false;
break;
}
}
// If not increasing after
// break point
if (!$flag)
return false;
else
{
// last element <= First element
if ($a[$n - 1] <= $a[0])
return true;
else
return false;
}
}
}
// Driver code
$arr = array( 3, 1, 2, 2, 3 );
$n = sizeof($arr);
if (isPossible($arr, $n))
echo "Possible";
else
echo "Not Possible";
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>
Producción:
Possible
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Consulte el artículo completo sobre Comprobar si es posible ordenar la array después de rotarla para obtener más detalles.
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