Dados dos números enteros positivos K y N , la tarea es encontrar la permutación presente en el medio de todas las permutaciones de longitud máxima N , que consta de números enteros del rango [1, K], ordenados lexicográficamente.
Ejemplos:
Entrada: K = 3, N = 2
Salida: 2 1
Explicación: El orden lexicográfico de todas las permutaciones posibles es:
- {1}.
- {1, 1}
- {1, 2}
- {1, 3}
- {2}
- {2, 1}
- {2, 2}
- {2, 3}
- {3}
- {3, 1}
- {3, 2}
- {3, 3}
Por lo tanto, la secuencia lexicográficamente más pequeña del medio es (N/2) th (= 6th ) secuencia, que es {2, 1}.
Entrada: K = 2, N = 4
Salida: 1 2 2 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las subsecuencias posibles de una longitud [1, N] , que consta de números enteros de [1, K] . Almacene estos elementos en una array. Después de generar todas las subsecuencias, ordene la lista almacenada de subsecuencias e imprima el elemento central de la lista.
Complejidad temporal: O(N K )
Espacio auxiliar: O(N K )
Enfoque eficiente: el enfoque anterior se puede optimizar verificando la paridad de K , ya sea que K sea impar o par, y luego encuentre lexicográficamente la secuencia más pequeña en el medio en consecuencia. Siga los pasos a continuación para resolver el problema:
- Si el valor de K es par , entonces exactamente la mitad de las secuencias comienzan con un número entero K/2 o menos. Por lo tanto, la secuencia resultante es K/2 seguida de (N – 1) aparición de K .
- Si el valor K es impar , considere B como una secuencia que contiene N ocurrencias de (K + 1)/2 .
- Para una secuencia X , sea f(X) una secuencia tal que X i en X se reemplaza con (K + 1 − X i ) .
- La única excepción ocurre con los prefijos de B .
- Comience con la secuencia B y realice los siguientes pasos (N – 1)/2 veces:
- Si el último elemento de la secuencia actual es 1 , elimínelo.
- De lo contrario, disminuya el último elemento en 1 , y mientras la secuencia contenga menos de N elementos, e inserte K al final de la secuencia B.
- Después de completar los pasos anteriores, imprima la secuencia obtenida en la array B[] .
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 that finds the middle the // lexicographical smallest sequence void lexiMiddleSmallest(int K, int N) { // If K is even if (K % 2 == 0) { // First element is K/2 cout << K / 2 << " "; // Remaining elements of the // sequence are all integer K for (int i = 0; i < N - 1; ++i) { cout << K << " "; } cout << "\n"; exit(0); } // Stores the sequence when K // is odd vector<int> a(N, (K + 1) / 2); // Iterate over the range [0, N/2] for (int i = 0; i < N / 2; ++i) { // Check if the sequence ends // with in 1 or not if (a.back() == 1) { // Remove the sequence // ending in 1 a.pop_back(); } // If it doesn't end in 1 else { // Decrement by 1 --a.back(); // Insert K to the sequence // till its size is N while ((int)a.size() < N) { a.push_back(K); } } } // Print the sequence stored // in the vector for (auto i : a) { cout << i << " "; } cout << "\n"; } // Driver Code int main() { int K = 2, N = 4; lexiMiddleSmallest(K, N); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function that finds the middle the // lexicographical smallest sequence static void lexiMiddleSmallest(int K, int N) { // If K is even if (K % 2 == 0) { // First element is K/2 System.out.print(K / 2 + " "); // Remaining elements of the // sequence are all integer K for (int i = 0; i < N - 1; ++i) { System.out.print(K + " "); } System.out.println(); return; } // Stores the sequence when K // is odd ArrayList<Integer> a = new ArrayList<Integer>(); // Iterate over the range [0, N/2] for (int i = 0; i < N / 2; ++i) { // Check if the sequence ends // with in 1 or not if (a.get(a.size() - 1) == 1) { // Remove the sequence // ending in 1 a.remove(a.size() - 1); } // If it doesn't end in 1 else { // Decrement by 1 int t = a.get(a.size() - 1) - 1; a.set(a.get(a.size() - 1), t); // Insert K to the sequence // till its size is N while (a.size() < N) { a.add(K); } } } // Print the sequence stored // in the vector for (int i : a) { System.out.print(i + " "); } System.out.println(); } // Driver Code public static void main(String[] args) { int K = 2, N = 4; lexiMiddleSmallest(K, N); } } // This code is contributed by Dharanendra L V.
Python3
# Python3 program for the above approach # Function that finds the middle the # lexicographical smallest sequence def lexiMiddleSmallest(K, N): # If K is even if (K % 2 == 0): # First element is K/2 print(K // 2,end=" ") # Remaining elements of the # sequence are all integer K for i in range(N - 1): print(K, end = " ") print() return # Stores the sequence when K # is odd a = [(K + 1) // 2]*(N) # Iterate over the range [0, N/2] for i in range(N//2): # Check if the sequence ends # with in 1 or not if (a[-1] == 1): # Remove the sequence # ending in 1 del a[-1] # If it doesn't end in 1 else: # Decrement by 1 a[-1] -= 1 # Insert K to the sequence # till its size is N while (len(a) < N): a.append(K) # Print sequence stored # in the vector for i in a: print(i, end = " ") print() # Driver Code if __name__ == '__main__': K, N = 2, 4 lexiMiddleSmallest(K, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function that finds the middle the // lexicographical smallest sequence static void lexiMiddleSmallest(int K, int N) { // If K is even if (K % 2 == 0) { // First element is K/2 Console.Write(K / 2 + " "); // Remaining elements of the // sequence are all integer K for (int i = 0; i < N - 1; ++i) { Console.Write(K + " "); } Console.WriteLine(); return; } // Stores the sequence when K // is odd List<int> a = new List<int>(); // Iterate over the range [0, N/2] for (int i = 0; i < N / 2; ++i) { // Check if the sequence ends // with in 1 or not if (a[a.Count - 1] == 1) { // Remove the sequence // ending in 1 a.Remove(a.Count - 1); } // If it doesn't end in 1 else { // Decrement by 1 a[a.Count - 1] -= 1; // Insert K to the sequence // till its size is N while ((int)a.Count < N) { a.Add(K); } } } // Print the sequence stored // in the vector foreach(int i in a) { Console.Write(i + " "); } Console.WriteLine(); } // Driver Code public static void Main() { int K = 2, N = 4; lexiMiddleSmallest(K, N); } } // This code is contributed by ukasp.
Javascript
<script> // javascript program for the above approach // Function that finds the middle the // lexicographical smallest sequence function lexiMiddleSmallest(K, N) { // If K is even if (K % 2 == 0) { // First element is K/2 document.write(K / 2 + " "); // Remaining elements of the // sequence are all integer K for (let i = 0; i < N - 1; ++i) { document.write(K + " "); } document.write("<br/>"); return; } // Stores the sequence when K // is odd let a = []; // Iterate over the range [0, N/2] for (let i = 0; i < N / 2; ++i) { // Check if the sequence ends // with in 1 or not if (a[a.length - 1] == 1) { // Remove the sequence // ending in 1 a.pop(a.length - 1); } // If it doesn't end in 1 else { // Decrement by 1 a[a.length - 1] -= 1; // Insert K to the sequence // till its size is N while (a.length < N) { a.push(K); } } } // Print the sequence stored // in the vector for(let i in a) { document.write(i + " "); } document.write("<br/>"); } // Driver Code let K = 2, N = 4; lexiMiddleSmallest(K, N); </script>
1 2 2 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por huzaifa0602 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA