Dada una array arr[] que consta de N enteros, la tarea es verificar si la array se puede ordenar intercambiando elementos adyacentes cualquier cantidad de veces, de modo que cada elemento de la array se intercambie incluso varias veces.
Ejemplos:
Entrada: arr[] = {4, 3, 2, 5}
Salida: Sí
Explicación:
A continuación se muestra el posible orden de intercambio para ordenar la array:
- Elija los índices 0 y 1 modifica la array a [3, 4, 2, 5]. Ahora, la frecuencia de intercambio de {2, 3, 4, 5} es {0, 1, 1, 0} respectivamente.
- Elegir los índices 1 y 2 modifica la array a [3, 2, 4, 5]. Ahora, la frecuencia de intercambio de {2, 3, 4, 5} es {1, 1, 2, 0} respectivamente.
- Elija los índices 0 y 1 modifica la array a [2, 3, 4, 5]. Ahora, la frecuencia de intercambio de {2, 3, 4, 5} es {2, 2, 2, 0} respectivamente.
Por lo tanto, cada elemento de la array se intercambia un número par de veces y se ordena la array dada. Por lo tanto, imprima Sí.
Entrada: arr[] = {1, 2, 3, 5, 4}
Salida: No
Enfoque: El problema dado puede resolverse observando el hecho de que dos elementos de índices pares o impares adyacentes pueden intercambiarse ya que no hay restricción en el número de intercambios sin cambiar el elemento central. Por lo tanto, la idea es reorganizar el elemento de la array en los respectivos índices pares e impares y verificar si la array formada está ordenada o no. Siga los pasos a continuación para resolver el problema dado:
- Almacene todos los elementos de la array arr[i] en los índices impares en otra array, digamos odd[] .
- Almacene todos los elementos de la array arr[i] en los índices pares en otra array, digamos even[] .
- Ordene las arrays impar[] y par[] en orden creciente.
- inicialice dos variables, digamos j y k como 0 que se usa para recorrer las arrays odd[] y even[] .
- Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
- Si el valor de i es impar, inserte el elemento impar[j] en la array res[] e incremente el valor de j en 1 .
- Si el valor de i es par , empuje el elemento par[k] en la array res[] e incremente el valor de j en 1 .
- Después de completar los pasos anteriores, si la array res[] está ordenada, imprima Yes . De lo contrario , imprima No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to check if the array can be // made sorted by adjacent swapping of // element such that each array element // is swapped even number of times bool isSorted(int arr[], int n) { vector<int> evenArr, oddArr; // Traverse the given array for (int i = 0; i < n; i++) { // Stores all the even positions // elements if (i % 2 == 0) evenArr.push_back(arr[i]); // Stores all the odd positions // elements else oddArr.push_back(arr[i]); } // Sort the array evenArr[] sort(evenArr.begin(), evenArr.end()); // Sort the array oddArr[] sort(oddArr.begin(), oddArr.end()); int j = 0, k = 0; vector<int> res; // Combine the elements from evenArr // and oddArr in the new array res[] for (int i = 0; i < n; i++) { if (i % 2 == 0) res.push_back(evenArr[j]), j++; else res.push_back(oddArr[k]), k++; } // Check if the array res[] is // sorted or not for (int i = 0; i < n - 1; i++) { if (res[i] > res[i + 1]) return false; } // Otherwise, return true return true; } // Driver Code int main() { int arr[] = { 4, 3, 2, 5 }; int N = sizeof(arr) / sizeof(arr[0]); if (isSorted(arr, N)) { cout << "Yes"; } else { cout << "No"; } return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if the array can be // made sorted by adjacent swapping of // element such that each array element // is swapped even number of times static boolean isSorted(int arr[], int n) { Vector<Integer> evenArr = new Vector<Integer>(); Vector<Integer> oddArr = new Vector<Integer>(); // Traverse the given array for (int i = 0; i < n; i++) { // Stores all the even positions // elements if (i % 2 == 0) evenArr.add(arr[i]); // Stores all the odd positions // elements else oddArr.add(arr[i]); } // Sort the array evenArr[] Collections.sort(evenArr); // Sort the array oddArr[] Collections.sort(oddArr); int j = 0, k = 0; Vector<Integer> res=new Vector<Integer>();; // Combine the elements from evenArr // and oddArr in the new array res[] for (int i = 0; i < n; i++) { if (i % 2 == 0) { res.add(evenArr.get(j)); j++; } else { res.add(oddArr.get(k)); k++; } } // Check if the array res[] is // sorted or not for (int i = 0; i < n - 1; i++) { if (res.get(i) > res.get(i + 1)) return false; } // Otherwise, return true return true; } // Driver Code public static void main(String[] args) { int arr[] = { 4, 3, 2, 5 }; int N = arr.length; if (isSorted(arr, N)) { System.out.print("Yes"); } else { System.out.print("No"); } } } // This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to check if the array can be # made sorted by adjacent swapping of # element such that each array element # is swapped even number of times def isSorted(arr, n): evenArr = [] oddArr = [] # Traverse the given array for i in range(n): # Stores all the even positions # elements if (i % 2 == 0): evenArr.append(arr[i]) # Stores all the odd positions # elements else: oddArr.append(arr[i]) # Sort the array evenArr[] evenArr.sort() # Sort the array oddArr[] oddArr.sort() j = 0 k = 0 res = [] # Combine the elements from evenArr # and oddArr in the new array res[] for i in range(n): if (i % 2 == 0): res.append(evenArr[j]) j += 1 else: res.append(oddArr[k]) k += 1 # Check if the array res[] is # sorted or not for i in range(n - 1): if (res[i] > res[i + 1]): return False # Otherwise, return true return True # Driver Code if __name__ == '__main__': arr = [ 4, 3, 2, 5 ] N = len(arr) if (isSorted(arr, N)): print("Yes") else: print("No") # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to check if the array can be // made sorted by adjacent swapping of // element such that each array element // is swapped even number of times static bool isSorted(int[] arr, int n) { List<int> evenArr = new List<int>(); List<int> oddArr = new List<int>(); // Traverse the given array for (int i = 0; i < n; i++) { // Stores all the even positions // elements if (i % 2 == 0) evenArr.Add(arr[i]); // Stores all the odd positions // elements else oddArr.Add(arr[i]); } // Sort the array evenArr[] evenArr.Sort(); // Sort the array oddArr[] oddArr.Sort(); int j = 0, k = 0; List<int> res = new List<int>(); // Combine the elements from evenArr // and oddArr in the new array res[] for (int i = 0; i < n; i++) { if (i % 2 == 0) { res.Add(evenArr[j]); j++; } else { res.Add(oddArr[k]); k++; } } // Check if the array res[] is // sorted or not for (int i = 0; i < n - 1; i++) { if (res[i] > res[i + 1]) return false; } // Otherwise, return true return true; } // Driver Code public static void Main() { int[] arr = { 4, 3, 2, 5 }; int N = arr.Length; if (isSorted(arr, N)) { Console.Write("Yes"); } else { Console.Write("No"); } } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript program for the above approach; // Function to check if the array can be // made sorted by adjacent swapping of // element such that each array element // is swapped even number of times function isSorted(arr, n) { let evenArr = [], oddArr = []; // Traverse the given array for (let i = 0; i < n; i++) { // Stores all the even positions // elements if (i % 2 == 0) evenArr.push(arr[i]); // Stores all the odd positions // elements else oddArr.push(arr[i]); } // Sort the array evenArr[] evenArr.sort(function (a, b) { return a - b }); // Sort the array oddArr[] oddArr.sort(function (a, b) { return a - b }); let j = 0, k = 0; let res = []; // Combine the elements from evenArr // and oddArr in the new array res[] for (let i = 0; i < n; i++) { if (i % 2 == 0) res.push(evenArr[j]), j++; else res.push(oddArr[k]), k++; } // Check if the array res[] is // sorted or not for (let i = 0; i < n - 1; i++) { if (res[i] > res[i + 1]) return false; } // Otherwise, return true return true; } // Driver Code let arr = [4, 3, 2, 5]; let N = arr.length; if (isSorted(arr, N)) { document.write("Yes"); } else { document.write("No"); } // This code is contributed by Potta Lokesh </script>
Yes
Complejidad temporal: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ashutoshtiwari22111998 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA