Dada una array de enteros arr[] , la tarea es ordenar solo aquellos elementos que son números feos en sus posiciones relativas en la array (las posiciones de otros elementos no deben verse afectadas).
Los números feos son números cuyos únicos factores primos son 2 , 3 o 5 .
La secuencia 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ….. muestra los primeros números feos. Por convención, 1 está incluido.
Ejemplos:
Entrada: arr[] = {13, 9, 11, 3, 2}
Salida: 13 2 11 3 9
9, 3 y 2 son los únicos números feos en la array dada.
Entrada: arr[] = {1, 2, 3, 7, 12, 10}
Salida: 1 2 3 7 10 12
Acercarse:
- Comience a recorrer la array y para cada elemento arr[i] , si arr[i] es un número feo, guárdelo en una ArrayList y actualice arr[i] = -1
- Después de que todos los números desagradables se hayan almacenado en ArrayList, ordene el ArrayList actualizado.
- Recorra nuevamente la array y para cada elemento,
- Si arr[i] = -1 , imprima el primer elemento de ArrayList que no se haya impreso antes.
- De lo contrario, imprime arr[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach #include<bits/stdc++.h> using namespace std; // Function that returns true if n is an ugly number bool isUgly(int n) { // While divisible by 2, keep dividing while (n % 2 == 0) n = n / 2; // While divisible by 3, keep dividing while (n % 3 == 0) n = n / 3; // While divisible by 5, keep dividing while (n % 5 == 0) n = n / 5; // n must be 1 if it was ugly if (n == 1) return true; return false; } // Function to sort ugly numbers // in their relative positions void sortUglyNumbers(int arr[], int n) { // To store the ugly numbers from the array vector<int> list; int i; for (i = 0; i < n; i++) { // If current element is an ugly number if (isUgly(arr[i])) { // Add it to the ArrayList // and set arr[i] to -1 list.push_back(arr[i]); arr[i] = -1; } } // Sort the ugly numbers sort(list.begin(),list.end()); int j = 0; for (i = 0; i < n; i++) { // Position of an ugly number if (arr[i] == -1) cout << list[j++] << " "; else cout << arr[i] << " "; } } // Driver code int main() { int arr[] = { 1, 2, 3, 7, 12, 10 }; int n = sizeof(arr)/sizeof(arr[0]); sortUglyNumbers(arr, n); } // This code is contributed by // Surendra_Gangwar
Java
// Java implementation of the approach import java.util.ArrayList; import java.util.Collections; class GFG { // Function that returns true if n is an ugly number static boolean isUgly(int n) { // While divisible by 2, keep dividing while (n % 2 == 0) n = n / 2; // While divisible by 3, keep dividing while (n % 3 == 0) n = n / 3; // While divisible by 5, keep dividing while (n % 5 == 0) n = n / 5; // n must be 1 if it was ugly if (n == 1) return true; return false; } // Function to sort ugly numbers // in their relative positions static void sortUglyNumbers(int arr[], int n) { // To store the ugly numbers from the array ArrayList<Integer> list = new ArrayList<>(); int i; for (i = 0; i < n; i++) { // If current element is an ugly number if (isUgly(arr[i])) { // Add it to the ArrayList // and set arr[i] to -1 list.add(arr[i]); arr[i] = -1; } } // Sort the ugly numbers Collections.sort(list); int j = 0; for (i = 0; i < n; i++) { // Position of an ugly number if (arr[i] == -1) System.out.print(list.get(j++) + " "); else System.out.print(arr[i] + " "); } } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3, 7, 12, 10 }; int n = arr.length; sortUglyNumbers(arr, n); } }
Python3
# Python3 implementation of the approach # Function that returns true if n is an ugly number def isUgly(n): # While divisible by 2, keep dividing while n % 2 == 0: n = n // 2 # While divisible by 3, keep dividing while n % 3 == 0: n = n // 3 # While divisible by 5, keep dividing while n % 5 == 0: n = n // 5 # n must be 1 if it was ugly if n == 1: return True return False # Function to sort ugly numbers # in their relative positions def sortUglyNumbers(arr, n): # To store the ugly numbers from the array list = [] for i in range(0, n): # If current element is an ugly number if isUgly(arr[i]): # Add it to the ArrayList # and set arr[i] to -1 list.append(arr[i]) arr[i] = -1 # Sort the ugly numbers list.sort() j = 0 for i in range(0, n): # Position of an ugly number if arr[i] == -1: print(list[j], end = " ") j += 1 else: print(arr[i], end = " ") # Driver code if __name__ == "__main__": arr = [1, 2, 3, 7, 12, 10] n = len(arr) sortUglyNumbers(arr, n) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function that returns true // if n is an ugly number static bool isUgly(int n) { // While divisible by 2, keep dividing while (n % 2 == 0) n = n / 2; // While divisible by 3, keep dividing while (n % 3 == 0) n = n / 3; // While divisible by 5, keep dividing while (n % 5 == 0) n = n / 5; // n must be 1 if it was ugly if (n == 1) return true; return false; } // Function to sort ugly numbers // in their relative positions static void sortUglyNumbers(int []arr, int n) { // To store the ugly numbers from the array List<int> list = new List<int>(); int i; for (i = 0; i < n; i++) { // If current element is an ugly number if (isUgly(arr[i])) { // Add it to the ArrayList // and set arr[i] to -1 list.Add(arr[i]); arr[i] = -1; } } // Sort the ugly numbers list.Sort(); int j = 0; for (i = 0; i < n; i++) { // Position of an ugly number if (arr[i] == -1) Console.Write(list[j++] + " "); else Console.Write(arr[i] + " "); } } // Driver code public static void Main(String[] args) { int []arr = { 1, 2, 3, 7, 12, 10 }; int n = arr.Length; sortUglyNumbers(arr, n); } } // This code contributed by Rajput-Ji
Javascript
<script> // Javascript implementation of the approach // Function that returns true if n is an ugly number function isUgly(n) { // While divisible by 2, keep dividing while (n % 2 == 0) n = n / 2; // While divisible by 3, keep dividing while (n % 3 == 0) n = n / 3; // While divisible by 5, keep dividing while (n % 5 == 0) n = n / 5; // n must be 1 if it was ugly if (n == 1) return true; return false; } // Function to sort ugly numbers // in their relative positions function sortUglyNumbers(arr, n) { // To store the ugly numbers from the array var list = []; var i; for (i = 0; i < n; i++) { // If current element is an ugly number if (isUgly(arr[i])) { // Add it to the ArrayList // and set arr[i] to -1 list.push(arr[i]); arr[i] = -1; } } // Sort the ugly numbers list.sort((a,b)=>a-b); var j = 0; for (i = 0; i < n; i++) { // Position of an ugly number if (arr[i] == -1) document.write( list[j++] + " "); else document.write( arr[i] + " "); } } // Driver code var arr = [1, 2, 3, 7, 12, 10 ]; var n = arr.length; sortUglyNumbers(arr, n); </script>
1 2 3 7 10 12
Complejidad de Tiempo: O(nlog(n))
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA