Comprobar si una array está ordenada y rotada

Dada una array de N enteros distintos. La tarea es escribir un programa para verificar si esta array está ordenada y girada en sentido contrario a las agujas del reloj. Una array ordenada no se considera ordenada y rotada, es decir, debe haber al menos una rotación.
Ejemplos
 

Input : arr[] = { 3, 4, 5, 1, 2 }
Output : YES
The above array is sorted and rotated.
Sorted array: {1, 2, 3, 4, 5}. 
Rotating this sorted array clockwise 
by 3 positions, we get: { 3, 4, 5, 1, 2}

Input: arr[] = {7, 9, 11, 12, 5}
Output: YES

Input: arr[] = {1, 2, 3}
Output: NO

Input: arr[] = {3, 4, 6, 1, 2, 5}
Output: NO

Enfoque
 

  • Encuentre el elemento mínimo en la array.
  • Ahora, si se ordena la array y luego se giran todos los elementos antes del elemento mínimo estarán en orden creciente y todos los elementos después del elemento mínimo también estarán en orden creciente.
  • Compruebe si todos los elementos antes del elemento mínimo están en orden creciente.
  • Compruebe si todos los elementos después del elemento mínimo están en orden creciente.
  • Compruebe si el último elemento de la array es más pequeño que el elemento inicial.
  • Si se cumplen las tres condiciones anteriores, imprima ; de lo contrario, imprima NO .

A continuación se muestra la implementación de la idea anterior: 
 

C++

// CPP program to check if an array is
// sorted and rotated clockwise
#include <climits>
#include <iostream>
 
using namespace std;
 
// Function to check if an array is
// sorted and rotated clockwise
void checkIfSortRotated(int arr[], int n)
{
    int minEle = INT_MAX;
    int maxEle = INT_MIN;
 
    int minIndex = -1;
 
    // Find the minimum element
    // and it's index
    for (int i = 0; i < n; i++) {
        if (arr[i] < minEle) {
            minEle = arr[i];
            minIndex = i;
        }
    }
 
    int flag1 = 1;
 
    // Check if all elements before minIndex
    // are in increasing order
    for (int i = 1; i < minIndex; i++) {
        if (arr[i] < arr[i - 1]) {
            flag1 = 0;
            break;
        }
    }
 
    int flag2 = 1;
 
    // Check if all elements after minIndex
    // are in increasing order
    for (int i = minIndex + 1; i < n; i++) {
        if (arr[i] < arr[i - 1]) {
            flag2 = 0;
            break;
        }
    }
 
    // Check if last element of the array
    // is smaller than the element just
    // starting element of the array
    // for arrays like [3,4,6,1,2,5] - not circular array
    if (flag1 && flag2 && (arr[n - 1] < arr[0]))
        cout << "YES";
    else
        cout << "NO";
}
 
// Driver code
int main()
{
    int arr[] = { 3, 4, 5, 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    checkIfSortRotated(arr, n);
    return 0;
}

Java

// Java program to check if an
// array is sorted and rotated
// clockwise
import java.io.*;
 
class GFG {
 
    // Function to check if an array is
    // sorted and rotated clockwise
    static void checkIfSortRotated(int arr[], int n)
    {
        int minEle = Integer.MAX_VALUE;
        int maxEle = Integer.MIN_VALUE;
 
        int minIndex = -1;
 
        // Find the minimum element
        // and it's index
        for (int i = 0; i < n; i++) {
            if (arr[i] < minEle) {
                minEle = arr[i];
                minIndex = i;
            }
        }
 
        boolean flag1 = true;
 
        // Check if all elements before
        // minIndex are in increasing order
        for (int i = 1; i < minIndex; i++) {
            if (arr[i] < arr[i - 1]) {
                flag1 = false;
                break;
            }
        }
 
        boolean flag2 = true;
 
        // Check if all elements after
        // minIndex are in increasing order
        for (int i = minIndex + 1; i < n; i++) {
            if (arr[i] < arr[i - 1]) {
                flag2 = false;
                break;
            }
        }
 
        // check if the minIndex is 0, i.e the first element
        // is the smallest , which is the case when array is
        // sorted but not rotated.
        if (minIndex == 0) {
            System.out.print("NO");
            return;
        }
        // Check if last element of the array
        // is smaller than the element just
        // before the element at minIndex
        // starting element of the array
        // for arrays like [3,4,6,1,2,5] - not sorted
        // circular array
        if (flag1 && flag2 && (arr[n - 1] < arr[0]))
            System.out.println("YES");
        else
            System.out.print("NO");
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 3, 4, 5, 1, 2 };
 
        int n = arr.length;
 
        // Function Call
        checkIfSortRotated(arr, n);
    }
}
 
// This code is contributed
// by inder_verma.

Python3

# Python3 program to check if an
# array is sorted and rotated clockwise
import sys
 
# Function to check if an array is
# sorted and rotated clockwise
 
 
def checkIfSortRotated(arr, n):
    minEle = sys.maxsize
    maxEle = -sys.maxsize - 1
    minIndex = -1
 
    # Find the minimum element
    # and it's index
    for i in range(n):
        if arr[i] < minEle:
            minEle = arr[i]
            minIndex = i
    flag1 = 1
 
    # Check if all elements before
    # minIndex are in increasing order
    for i in range(1, minIndex):
        if arr[i] < arr[i - 1]:
            flag1 = 0
            break
    flag2 = 2
 
    # Check if all elements after
    # minIndex are in increasing order
    for i in range(minIndex + 1, n):
        if arr[i] < arr[i - 1]:
            flag2 = 0
            break
 
    # Check if last element of the array
    # is smaller than the element just
    # before the element at minIndex
    # starting element of the array
    # for arrays like [3,4,6,1,2,5] - not sorted circular array
    if (flag1 and flag2 and
            arr[n - 1] < arr[0]):
        print("YES")
    else:
        print("NO")
 
 
# Driver code
arr = [3, 4, 5, 1, 2]
n = len(arr)
 
# Function Call
checkIfSortRotated(arr, n)
 
# This code is contributed
# by Shrikant13

C#

// C# program to check if an
// array is sorted and rotated
// clockwise
using System;
 
class GFG {
 
    // Function to check if an array is
    // sorted and rotated clockwise
    static void checkIfSortRotated(int[] arr, int n)
    {
        int minEle = int.MaxValue;
        // int maxEle = int.MinValue;
 
        int minIndex = -1;
 
        // Find the minimum element
        // and it's index
        for (int i = 0; i < n; i++) {
            if (arr[i] < minEle) {
                minEle = arr[i];
                minIndex = i;
            }
        }
 
        bool flag1 = true;
 
        // Check if all elements before
        // minIndex are in increasing order
        for (int i = 1; i < minIndex; i++) {
            if (arr[i] < arr[i - 1]) {
                flag1 = false;
                break;
            }
        }
 
        bool flag2 = true;
 
        // Check if all elements after
        // minIndex are in increasing order
        for (int i = minIndex + 1; i < n; i++) {
            if (arr[i] < arr[i - 1]) {
                flag2 = false;
                break;
            }
        }
 
        // Check if last element of the array
        // is smaller than the element just
        // before the element at minIndex
        // starting element of the array
        // for arrays like [3,4,6,1,2,5] - not circular
        // array
        if (flag1 && flag2 && (arr[n - 1] < arr[0]))
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 3, 4, 5, 1, 2 };
 
        int n = arr.Length;
         
          // Function Call
        checkIfSortRotated(arr, n);
    }
}
 
// This code is contributed
// by inder_verma.

PHP

<?php
// PHP program to check if an
// array is sorted and rotated
// clockwise
 
// Function to check if an array
// is sorted and rotated clockwise
function checkIfSortRotated($arr, $n)
{
    $minEle = PHP_INT_MAX;
    $maxEle = PHP_INT_MIN;
 
    $minIndex = -1;
 
    // Find the minimum element
    // and it's index
    for ($i = 0; $i <$n; $i++)
    {
        if ($arr[$i] < $minEle)
        {
            $minEle = $arr[$i];
            $minIndex = $i;
        }
    }
 
    $flag1 = 1;
 
    // Check if all elements before
    // minIndex are in increasing order
    for ( $i = 1; $i <$minIndex; $i++)
    {
        if ($arr[$i] < $arr[$i - 1])
        {
            $flag1 = 0;
            break;
        }
    }
 
    $flag2 = 1;
 
    // Check if all elements after
    // minIndex are in increasing order
    for ($i = $minIndex + 1; $i <$n; $i++)
    {
        if ($arr[$i] < $arr[$i - 1])
        {
            $flag2 = 0;
            break;
        }
    }
 
    // Check if last element of the array
    // is smaller than the element just
    // starting element of the array
    // for arrays like [3,4,6,1,2,5] - not sorted circular array
    if ($flag1 && $flag2 &&
       ($arr[$n - 1] < $arr[$0]))
        echo( "YES");
    else
        echo( "NO");
}
 
// Driver code
$arr = array(3, 4, 5, 1, 2);
 
//Function Call
$n = count($arr);
 
checkIfSortRotated($arr, $n);
 
// This code is contributed
// by inder_verma.
?>

Javascript

<script>
    // Javascript program to check if an
    // array is sorted and rotated
    // clockwise
     
    // Function to check if an array is
    // sorted and rotated clockwise
    function checkIfSortRotated(arr, n)
    {
        let minEle = Number.MAX_VALUE;
        // int maxEle = int.MinValue;
  
        let minIndex = -1;
  
        // Find the minimum element
        // and it's index
        for (let i = 0; i < n; i++) {
            if (arr[i] < minEle) {
                minEle = arr[i];
                minIndex = i;
            }
        }
  
        let flag1 = true;
  
        // Check if all elements before
        // minIndex are in increasing order
        for (let i = 1; i < minIndex; i++) {
            if (arr[i] < arr[i - 1]) {
                flag1 = false;
                break;
            }
        }
  
        let flag2 = true;
  
        // Check if all elements after
        // minIndex are in increasing order
        for (let i = minIndex + 1; i < n; i++) {
            if (arr[i] < arr[i - 1]) {
                flag2 = false;
                break;
            }
        }
  
        // Check if last element of the array
        // is smaller than the element just
        // before the element at minIndex
        // starting element of the array
        // for arrays like [3,4,6,1,2,5] - not circular
        // array
        if (flag1 && flag2 && (arr[n - 1] < arr[0]))
            document.write("YES");
        else
            document.write("NO");
    }
     
    let arr = [ 3, 4, 5, 1, 2 ];
  
    let n = arr.length;
 
    // Function Call
    checkIfSortRotated(arr, n);
 
// This code is contributed by mukesh07.
</script>
Producción

YES

Método 2: 

Acercarse:  

  • Tome dos variables, digamos x e y, inicializadas como 0.
  • Ahora atraviesa la array.
  • Si encontramos que el elemento anterior es más pequeño que el actual, aumentamos x en uno.
  • De lo contrario, si encontramos que el elemento anterior es mayor que el actual, aumentamos y en uno.
  • Después del recorrido, si alguno de xey no es igual a 1, devuelve falso.
  • Si cualquiera de x o y es 1, entonces compare el último elemento con el primer elemento (el elemento 0 como el actual y el último elemento como el anterior). Es decir, si el último elemento es mayor, aumente y en uno; de lo contrario, aumente x en uno.
  • Nuevamente verifique x e y, si alguno es igual a uno, devuelva verdadero. es decir, la array está ordenada y girada. De lo contrario, devuelve falso.

Explicación: 

  • La idea es sencilla. Si la array se ordena y rota, los elementos aumentan o disminuyen, pero con una excepción. Entonces contamos cuántas veces el elemento es mayor que su elemento anterior, y cuántas veces el elemento es más pequeño que su elemento anterior. 
  • El caso especial es cuando la array está ordenada pero no rotada. para esto verifique el último elemento con el primer elemento especialmente.

A continuación se muestra la implementación del enfoque anterior:

C++

#include <bits/stdc++.h>
using namespace std;
 
bool checkRotatedAndSorted(int arr[], int n)
{
 
    // Your code here
    // Initializing two variables x,y as zero.
    int x = 0, y = 0;
 
    // Traversing array 0 to last element.
    // n-1 is taken as we used i+1.
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] < arr[i + 1])
            x++;
        else
            y++;
    }
 
    // If till now both x,y are greater than 1 means
    // array is not sorted. If both any of x,y is zero
    // means array is not rotated.
    if (x == 1 || y == 1) {
        // Checking for last element with first.
        if (arr[n - 1] < arr[0])
            x++;
        else
            y++;
 
        // Checking for final result.
        if (x == 1 || y == 1)
            return true;
    }
 
    // If still not true then definitely false.
    return false;
}
 
//  Driver Code Starts.
 
int main()
{
    int arr[] = { 4, 5, 1, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    if (checkRotatedAndSorted(arr, n))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
     
  return 0;
}

Java

import java.io.*;
 
class GFG {
 
    // Function to check if an array is
    // Sorted and rotated clockwise
    static boolean checkIfSortRotated(int arr[], int n)
    {
        // Initializing two variables x,y as zero.
        int x = 0, y = 0;
 
        // Traversing array 0 to last element.
        // n-1 is taken as we used i+1.
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] < arr[i + 1])
                x++;
            else
                y++;
        }
 
        // If till now both x,y are greater
        // than 1 means array is not sorted.
        // If both any of x,y is zero means
        // array is not rotated.
        if (x == 1 || y == 1) {
            // Checking for last element with first.
            if (arr[n - 1] < arr[0])
                x++;
            else
                y++;
 
            // Checking for final result.
            if (x == 1 || y == 1)
                return true;
        }
        // If still not true then definitely false.
        return false;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 5, 1, 2, 3, 4 };
 
        int n = arr.length;
 
        // Function Call
        boolean x = checkIfSortRotated(arr, n);
        if (x == true)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}

Python3

def checkRotatedAndSorted(arr, n):
 
    # Your code here
    # Initializing two variables x,y as zero.
    x = 0
    y = 0
 
    # Traversing array 0 to last element.
    # n-1 is taken as we used i+1.
    for i in range (n-1):
        if (arr[i] < arr[i + 1]):
            x += 1
        else:
            y += 1
     
 
    # If till now both x,y are greater than 1 means
    # array is not sorted. If both any of x,y is zero
    # means array is not rotated.
    if (x == 1 or y == 1):
        # Checking for last element with first.
        if (arr[n - 1] < arr[0]):
            x += 1
        else:
            y += 1
 
        # Checking for final result.
        if (x == 1 or y == 1):
            return True
     
    # If still not true then definitely false.
    return False
 
# Driver Code Starts.
arr = [ 4, 5, 1, 2, 3 ]
n = len(arr)
 
# Function Call
if (checkRotatedAndSorted(arr, n)):
    print("YES")
else:
    print("NO")
 
# This code is contributed by shivanisinghss2110

C#

using System;
public class GFG {
 
    // Function to check if an array is
    // Sorted and rotated clockwise
    static bool checkIfSortRotated(int []arr, int n)
    {
        // Initializing two variables x,y as zero.
        int x = 0, y = 0;
 
        // Traversing array 0 to last element.
        // n-1 is taken as we used i+1.
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] < arr[i + 1])
                x++;
            else
                y++;
        }
 
        // If till now both x,y are greater
        // than 1 means array is not sorted.
        // If both any of x,y is zero means
        // array is not rotated.
        if (x == 1 || y == 1) {
            // Checking for last element with first.
            if (arr[n - 1] < arr[0])
                x++;
            else
                y++;
 
            // Checking for readonly result.
            if (x == 1 || y == 1)
                return true;
        }
        // If still not true then definitely false.
        return false;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = { 5, 1, 2, 3, 4 };
 
        int n = arr.Length;
 
        // Function Call
        bool x = checkIfSortRotated(arr, n);
        if (x == true)
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
}
 
// This code is contributed by umadevi9616

Javascript

<script>
// JavaScript Function to check if an array is
// Sorted and rotated clockwise
function checkIfSortRotated(arr, n)
    {
     
        // Initializing two variables x,y as zero.
        var x = 0, y = 0;
 
        // Traversing array 0 to last element.
        // n-1 is taken as we used i+1.
        for (var i = 0; i < n - 1; i++) {
            if (arr[i] < arr[i + 1])
                x++;
            else
                y++;
        }
 
        // If till now both x,y are greater
        // than 1 means array is not sorted.
        // If both any of x,y is zero means
        // array is not rotated.
        if (x == 1 || y == 1) {
            // Checking for last element with first.
            if (arr[n - 1] < arr[0])
                x++;
            else
                y++;
 
            // Checking for final result.
            if (x == 1 || y == 1)
                return true;
        }
        // If still not true then definitely false.
        return false;
    }
 
    // Driver code
        var arr = [ 5, 1, 2, 3, 4 ];
 
        var n = arr.length;
 
        // Function Call
        var x = checkIfSortRotated(arr, n);
        if (x == true)
            document.write("YES");
        else
            document.write("NO");
 
// This code is contributed by shivanisinghss2110
</script>
Producción

YES

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por barykrg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *