Escriba código para encontrar el mínimo lexicográfico en una array circular, por ejemplo, para la array BCABDADAB, el mínimo lexicográfico es ABBCABDAD
Restricción de entrada: 1 < n < 1000
Ejemplos:
Input: GEEKSQUIZ Output: EEKSQUIZG Input: GFG Output: FGG Input : CAPABCQ Output : ABCQCAP
Hemos discutido una solución O(n 2 Logn) en Rotación lexicográficamente mínima de strings | conjunto 1 . Aquí necesitamos encontrar el índice inicial de rotación mínima y luego imprimir la rotación.
1) Initially assume 0 to be current min starting index. 2) Loop through i = 1 to n-1. a) For each i compare sequence starting at i with current min starting index b) If sequence starting at i is lexicographically smaller, update current min starting index.
Aquí está el pseudocódigo para el algoritmo.
function findIndexForSmallestSequence(S, n): result = 0 for i = 1:n-1 if (sequence beginning at i < sequence beginning at result) result = i end if end for return result
Aquí está la implementación del algoritmo anterior.
Python 3
# Python 3 program to find lexicographically # smallest sequence with rotations. # Function to compare lexicographically # two sequence with different starting # indexes. It returns true if sequence # beginning with y is lexicographically # greater. import copy def printSmallestSequence(s): m = copy.copy(s) for i in range(len(s) - 1): if m > s[i:] + s[:i]: m = s[i:] + s[:i] return m #Driver Code if __name__ == '__main__': st = 'DCACBCAA' print(printSmallestSequence(st)) # This code is contributed by Koushik Reddy B
Producción:
AADCACBC
Complejidad de tiempo: O (n ^ 2)
Espacio auxiliar: O (1)
Consulte el artículo completo sobre la secuencia rotada lexicográficamente más pequeña | Set 2 para más detalles!
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