Dada una array arr[] que consta de N pares , donde cada par representa el valor y la identificación respectivamente, la tarea es verificar si es posible ordenar la array por el primer elemento intercambiando solo pares que tienen diferentes identificaciones . Si es posible ordenar, imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {{340000, 2}, {45000, 1}, {30000, 2}, {50000, 4}}
Salida: Sí
Explicación:
una de las formas posibles de ordenar la array es intercambiar la array elementos en el siguiente orden:
- Swap, arr[0] y arr[3] , que modifica la array a arr[] = {{50000, 4}, {45000, 1}, {30000, 2}, {340000, 2}}.
- Swap, arr[0] y arr[2] , que modifica la array a arr[] = {{30000, 2}, {45000, 1}, {50000, 4}, {340000, 2}}.
Por lo tanto, después de los pasos anteriores, la array dada se ordena por el primer elemento.
Entrada: arr[] = {{15000, 2}, {34000, 2}, {10000, 2}}
Salida: No
Enfoque: el problema dado se puede resolver en función de la observación de que la array se puede ordenar si existen dos elementos de la array con ID diferentes . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos X que almacena la ID del par en el índice 0 .
- Recorra la array arr[] y, si existe algún par cuyo ID sea diferente de X , imprima «Sí» y salga del bucle .
- Después de completar los pasos anteriores, si todos los elementos tienen los mismos ID y si la array ya está ordenada , imprima «Sí» . De lo contrario, escriba «No» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if an // array is sorted or not bool isSorted(pair<int, int>* arr, int N) { // Traverse the array arr[] for (int i = 1; i < N; i++) { if (arr[i].first > arr[i - 1].first) { return false; } } // Return true return true; } // Function to check if it is possible // to sort the array w.r.t. first element string isPossibleToSort( pair<int, int>* arr, int N) { // Stores the ID of the first element int group = arr[0].second; // Traverse the array arr[] for (int i = 1; i < N; i++) { // If arr[i].second is not // equal to that of the group if (arr[i].second != group) { return "Yes"; } } // If array is sorted if (isSorted(arr, N)) { return "Yes"; } else { return "No"; } } // Driver Code int main() { pair<int, int> arr[] = { { 340000, 2 }, { 45000, 1 }, { 30000, 2 }, { 50000, 4 } }; int N = sizeof(arr) / sizeof(arr[0]); cout << isPossibleToSort(arr, N); return 0; }
Java
// java program for the above approach import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Function to check if an // array is sorted or not static boolean isSorted(int[][] arr, int N) { // Traverse the array arr[] for (int i = 1; i < N; i++) { if (arr[i][0] > arr[i - 1][0]) { return false; } } // Return true return true; } // Function to check if it is possible // to sort the array w.r.t. first element static String isPossibleToSort(int[][] arr, int N) { // Stores the ID of the first element int group = arr[0][1]; // Traverse the array arr[] for (int i = 1; i < N; i++) { // If arr[i].second is not // equal to that of the group if (arr[i][1] != group) { return "Yes"; } } // If array is sorted if (isSorted(arr, N)) { return "Yes"; } else { return "No"; } } // Driver Code public static void main(String[] args) { int arr[][] = { { 340000, 2 }, { 45000, 1 }, { 30000, 2 }, { 50000, 4 } }; int N = arr.length; System.out.print(isPossibleToSort(arr, N)); } } // This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to check if an # array is sorted or not def isSorted(arr, N): # Traverse the array arr[] for i in range(1, N): if (arr[i][0] > arr[i - 1][0]): return False # Return true return True # Function to check if it is possible # to sort the array w.r.t. first element def isPossibleToSort(arr, N): # Stores the ID of the first element group = arr[0][1] # Traverse the array arr[] for i in range(1, N): # If arr[i][1] is not # equal to that of the group if (arr[i][1] != group): return "Yes" # If array is sorted if (isSorted(arr, N)): return "Yes" else: return "No" # Driver Code if __name__ == '__main__': arr = [ [ 340000, 2 ], [ 45000, 1 ],[ 30000, 2 ], [ 50000, 4 ] ] N = len(arr) print (isPossibleToSort(arr, N)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; class GFG { // Function to check if an // array is sorted or not static bool isSorted(int[, ] arr, int N) { // Traverse the array arr[] for (int i = 1; i < N; i++) { if (arr[i, 0] > arr[i - 1, 0]) { return false; } } // Return true return true; } // Function to check if it is possible // to sort the array w.r.t. first element static string isPossibleToSort(int[, ] arr, int N) { // Stores the ID of the first element int group = arr[0, 1]; // Traverse the array arr[] for (int i = 1; i < N; i++) { // If arr[i].second is not // equal to that of the group if (arr[i, 1] != group) { return "Yes"; } } // If array is sorted if (isSorted(arr, N)) { return "Yes"; } else { return "No"; } } // Driver Code public static void Main() { int[, ] arr = { { 340000, 2 }, { 45000, 1 }, { 30000, 2 }, { 50000, 4 } }; int N = arr.GetLength(0); Console.WriteLine(isPossibleToSort(arr, N)); } } // This code is contributed by ukasp.
Javascript
<script> // Javascript program for the above approach // Function to check if an // array is sorted or not function isSorted(arr, N) { // Traverse the array arr[] for (let i = 1; i < N; i++) { if (arr[i][0] > arr[i - 1][0]) { return false; } } // Return true return true; } // Function to check if it is possible // to sort the array w.r.t. first element function isPossibleToSort(arr, N) { // Stores the ID of the first element let group = arr[0][1]; // Traverse the array arr[] for (let i = 1; i < N; i++) { // If arr[i].second is not // equal to that of the group if (arr[i][1] != group) { return "Yes"; } } // If array is sorted if (isSorted(arr, N)) { return "Yes"; } else { return "No"; } } // Driver Code let arr = [[340000, 2], [15000, 2], [34000, 2], [10000, 2]]; let N = arr.length; document.write(isPossibleToSort(arr, N)); // This code is contributed by Hritik </script>
Yes
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA