Verifique si una array dada es una array ordenada o no

Dada una array de n elementos distintos. Compruebe si la array dada es una array ordenada k o no. Una array ordenada k es una array en la que cada elemento está como máximo a k distancias de su posición de destino en la array ordenada. 

Por ejemplo, consideremos k es 2, un elemento en el índice 7 en la array ordenada, puede estar en los índices 5, 6, 7, 8, 9 en la array dada.

Ejemplos: 

Input : arr[] = {3, 2, 1, 5, 6, 4}, k = 2
Output : Yes
Every element is at most 2 distance away
from its target position in the sorted array.

Input : arr[] = {13, 8, 10, 7, 15, 14, 12}, k = 3
Output : No
13 is more than k = 3 distance away
from its target position in the sorted array. 

Copie elementos de la array original arr[] en una array auxiliar aux[]
Ordenar aux[] . Ahora, para cada elemento en el índice i en arr[] , encuentre su índice j en aux[] usando la búsqueda binaria. Si para cualquier elemento k < abs(ij) , entonces arr[] no es un arreglo k ordenado. De lo contrario, es una array ordenada k . Aquí los abdominales son el valor absoluto.

Implementación:

C++

// C++ implementation to check whether the given array
// is a k sorted array or not
#include <bits/stdc++.h>
using namespace std;
 
// function to find index of element 'x' in sorted 'arr'
// uses binary search technique
int binarySearch(int arr[], int low, int high, int x)
{
    while (low <= high)
    {
        int mid = (low + high) / 2;
         
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] > x)
            high = mid - 1;
        else   
            low = mid + 1;   
    }
}
 
// function to check whether the given array is
// a 'k' sorted array or not
string isKSortedArray(int arr[], int n, int k)
{
    // auxiliary array 'aux'
    int aux[n];
     
    // copy elements of 'arr' to 'aux'
    for (int i = 0; i<n; i++)
        aux[i] = arr[i];
     
    // sort 'aux'   
    sort(aux, aux + n);
     
    // for every element of 'arr' at index 'i',
    // find its index 'j' in 'aux'
    for (int i = 0; i<n; i++)
    {
        // index of arr[i] in sorted array 'aux'
        int j = binarySearch(aux, 0, n-1, arr[i]);
         
        // if abs(i-j) > k, then that element is
        // not at-most k distance away from its
        // target position. Thus,  'arr' is not a
        // k sorted array
        if (abs(i - j) > k)
            return "No";
    }
     
    // 'arr' is a k sorted array
    return "Yes";   
}
 
// Driver program to test above
int main()
{
    int arr[] = {3, 2, 1, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << "Is it a k sorted array?: "
         << isKSortedArray(arr, n, k);
    return 0;    
}

Java

// Java implementation to check whether the given array
// is a k sorted array or not
 
import java.util.Arrays;
 
class Test
{
    // Method to check whether the given array is
    // a 'k' sorted array or not
    static String isKSortedArray(int arr[], int n, int k)
    {
        // auxiliary array 'aux'
        int aux[] = new int[n];
          
        // copy elements of 'arr' to 'aux'
        for (int i = 0; i<n; i++)
            aux[i] = arr[i];
          
        // sort 'aux'   
        Arrays.sort(aux);
          
        // for every element of 'arr' at index 'i',
        // find its index 'j' in 'aux'
        for (int i = 0; i<n; i++)
        {
            // index of arr[i] in sorted array 'aux'
            int j = Arrays.binarySearch(aux,arr[i]);
              
            // if abs(i-j) > k, then that element is
            // not at-most k distance away from its
            // target position. Thus,  'arr' is not a
            // k sorted array
            if (Math.abs(i - j) > k)
                return "No";
        }
          
        // 'arr' is a k sorted array
        return "Yes";   
    }
 
    // Driver method
    public static void main(String args[])
    {
        int arr[] = {3, 2, 1, 5, 6, 4};
        int k = 2;
         
        System.out.println("Is it a k sorted array ?: " +
                            isKSortedArray(arr, arr.length, k));
    }
}

Python3

# Python 3 implementation to check
# whether the given array is a k
# sorted array or not
 
# function to find index of element
# 'x' in sorted 'arr' uses binary
# search technique
def binarySearch(arr, low, high, x):
    while (low <= high):
        mid = int((low + high) / 2)
         
        if (arr[mid] == x):
            return mid
        elif(arr[mid] > x):
            high = mid - 1
        else:
            low = mid + 1
 
# function to check whether the given
# array is a 'k' sorted array or not
def isKSortedArray(arr, n, k):
     
    # auxiliary array 'aux'
    aux = [0 for i in range(n)]
     
    # copy elements of 'arr' to 'aux'
    for i in range(0, n, 1):
        aux[i] = arr[i]
     
    # sort 'aux'
    aux.sort(reverse = False)
     
    # for every element of 'arr' at
    # index 'i', find its index 'j' in 'aux'
    for i in range(0, n, 1):
         
        # index of arr[i] in sorted
        # array 'aux'
        j = binarySearch(aux, 0, n - 1, arr[i])
         
        # if abs(i-j) > k, then that element is
        # not at-most k distance away from its
        # target position. Thus, 'arr' is not a
        # k sorted array
        if (abs(i - j) > k):
            return "No"
     
    # 'arr' is a k sorted array
    return "Yes"
 
# Driver Code
if __name__ == '__main__':
    arr = [3, 2, 1, 5, 6, 4]
    n = len(arr)
    k = 2
    print("Is it a k sorted array?:",
           isKSortedArray(arr, n, k))
 
# This code is contributed by
# Shashank_Sharma

C#

// C# implementation to check
// whether the given array is a
// k sorted array or not
using System;
using System.Collections;
 
class GFG {
     
    // Method to check whether the given
    // array is a 'k' sorted array or not
    static String isKSortedArray(int []arr, int n, int k)
    {
        // auxiliary array 'aux'
        int []aux = new int[n];
         
        // copy elements of 'arr' to 'aux'
        for (int i = 0; i<n; i++)
            aux[i] = arr[i];
         
        // sort 'aux'
        Array.Sort(aux);
         
        // for every element of 'arr' at index
        // 'i', find its index 'j' in 'aux'
        for (int i = 0; i<n; i++)
        {
            // index of arr[i] in sorted array 'aux'
            int j = Array.BinarySearch(aux,arr[i]);
             
            // if abs(i-j) > k, then that element is
            // not at-most k distance away from its
            // target position. Thus, 'arr' is not a
            // k sorted array
            if (Math.Abs(i - j) > k)
                return "No";
        }
         
        // 'arr' is a k sorted array
        return "Yes";
    }
 
    // Driver method
    public static void Main()
    {
        int []arr = {3, 2, 1, 5, 6, 4};
        int k = 2;
         
        Console.WriteLine("Is it a k sorted array ?: " +
                           isKSortedArray(arr, arr.Length, k));
    }
}
 
// This code is contributed by Sam007

Javascript

<script>
  
// Javascript implementation to check whether the given array
// is a k sorted array or not
 
// function to find index of element 'x' in sorted 'arr'
// uses binary search technique
function binarySearch(arr, low, high, x)
{
    while (low <= high)
    {
        var mid = parseInt((low + high) / 2);
         
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] > x)
            high = mid - 1;
        else   
            low = mid + 1;   
    }
}
 
// function to check whether the given array is
// a 'k' sorted array or not
function isKSortedArray(arr, n, k)
{
    // auxiliary array 'aux'
    var aux = Array(n);
 
    // copy elements of 'arr' to 'aux'
    for (var i = 0; i<n; i++)
        aux[i] = arr[i];
     
    // sort 'aux'   
    aux.sort((a,b)=> a-b)
     
    // for every element of 'arr' at index 'i',
    // find its index 'j' in 'aux'
    for (var i = 0; i<n; i++)
    {
        // index of arr[i] in sorted array 'aux'
        var j = binarySearch(aux, 0, n-1, arr[i]);
         
        // if abs(i-j) > k, then that element is
        // not at-most k distance away from its
        // target position. Thus,  'arr' is not a
        // k sorted array
        if (Math.abs(i - j) > k)
            return "No";
    }
     
    // 'arr' is a k sorted array
    return "Yes";   
}
 
// Driver program to test above
var arr = [3, 2, 1, 5, 6, 4];
var n = arr.length;
var k = 2;
document.write( "Is it a k sorted array?: "
      + isKSortedArray(arr, n, k));
 
 
</script>
Producción

Is it a k sorted array?: Yes

Complejidad temporal: O(nlogn) 
Espacio auxiliar: O(n)

Otro enfoque puede ser almacenar los índices correspondientes de los elementos en la array auxiliar . Luego simplemente verifique si   abs (i – aux[i].segundo) <= k, devuelva “No” si la condición no se cumple. Es un poco más rápido que el enfoque mencionado anteriormente, ya que no tenemos que realizar una búsqueda binaria para verificar la distancia desde el índice original, aunque la «notación O» seguirá siendo la misma.

Implementación:

C++

#include <bits/stdc++.h>
using namespace std;
 
string isKSortedArray(int arr[], int n, int k)
{
  // creating an array to store value, index of the original array
  vector<pair<int, int>> aux;
   
  for(int i=0;i<n;i++){
    aux.push_back({arr[i], i}); //  pushing the elements and index of arr to aux
  }
   
  // sorting the aux array
  sort(aux.begin(), aux.end());
   
  //  for every element, check if the absolute value of (currIndex-originalIndex) <= k
  //  if not, then return "NO"
  for(auto i=0;i<n;i++){
    if(abs(i-aux[i].second)>k) return "No";
     
  }
   
  // If all elements satisfy the condition, the loop will terminate and
  // "Yes" will be returned.
  return "Yes";
}
 
int main() {
    int arr[] = {3, 2, 1, 5, 6, 4}; //  input array
      int n = sizeof(arr)/sizeof(int); // number of elements in array(arr)
      int k = 2; // value to check is array is "k" sorted
   
    cout<<isKSortedArray(arr, n, k); // prints "Yes" since the input array is k-sorted
   
    return 0;
}

Python3

# Python code for the same approach
def isKSortedArray(arr, n, k):
 
    # creating an array to store value, index of the original array
    aux = []
 
    for i in range(n):
        aux.append([arr[i], i]) # pushing the elements and index of arr to aux
 
    # sorting the aux array
    aux.sort()
 
    # for every element, check if the absolute value of (currIndex-originalIndex) <= k
    # if not, then return "NO"
    for i in range(n):
        if(abs(i-aux[i][1])>k):
            return "No"
 
    # If all elements satisfy the condition, the loop will terminate and
    # "Yes" will be returned.
    return "Yes"
 
# driver code
 
arr = [3, 2, 1, 5, 6, 4] # input array
n = len(arr) # number of elements in array(arr)
k = 2 # value to check is array is "k" sorted
 
print(isKSortedArray(arr, n, k)) # prints "Yes" since the input array is k-sorted
 
# This code is contributed by shinjanpatra
Producción

Yes

Complejidad de tiempo: O(nlogn)
Complejidad de espacio: O(n)

Este artículo es una contribución de Ayush Jauhari y Naman Monga . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

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

Deja una respuesta

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