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.
C++
// C++ program to find lexicographically // smallest sequence with rotations. #include <iostream> using namespace std; // Function to compare lexicographically // two sequence with different starting // indexes. It returns true if sequence // beginning with y is lexicographically // greater. bool compareSeq(char S[], int x, int y, int n) { for (int i = 0; i < n; i++) { if (S[x] < S[y]) return false; else if (S[x] > S[y]) return true; x = (x + 1) % n; y = (y + 1) % n; } return true; } // Function to find starting index // of lexicographically smallest sequence int smallestSequence(char S[], int n) { int index = 0; for (int i = 1; i < n; i++) // if new sequence is smaller if (compareSeq(S, index, i, n)) // change index of current min index = i; return index; } // Function to print lexicographically // smallest sequence void printSmallestSequence(char S[], int n) { int starting_index = smallestSequence(S, n); for (int i = 0; i < n; i++) cout << S[(starting_index + i) % n]; } // driver code int main() { char S[] = "DCACBCAA"; int n = 8; printSmallestSequence(S, n); return 0; }
Java
// Java program to find lexicographically // smallest sequence with rotations. import java.util.*; import java.lang.*; import java.io.*; /* Name of the class */ class LexoSmallest { // Function to compare lexicographically // two sequence with different starting // indexes. It returns true if sequence // beginning with y is lexicographically // greater. static boolean compareSeq(char[] S, int x, int y, int n) { for (int i = 0; i < n; i++) { if (S[x] < S[y]) return false; else if (S[x] > S[y]) return true; x = (x + 1) % n; y = (y + 1) % n; } return true; } // Function to find starting index // of lexicographically smallest sequence static int smallestSequence(char[] S, int n) { int index = 0; for (int i = 1; i < n; i++) // if new sequence is smaller if (compareSeq(S, index, i, n)) // change index of current min index = i; return index; } // Function to print lexicographically // smallest sequence static void printSmallestSequence(String str, int n) { char[] S = str.toCharArray(); int starting_index = smallestSequence(S, n); for (int i = 0; i < n; i++) System.out.print(S[(starting_index + i) % n]); } // driver code public static void main(String[] args) { String S = "DCACBCAA"; int n = 8; printSmallestSequence(S, n); } } // This code is contributed by Mr Somesh Awasthi
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
C#
// C# program to find lexicographically // smallest sequence with rotations. using System; class LexoSmallest { // Function to compare lexicographically // two sequence with different starting // indexes. It returns true if sequence // beginning with y is lexicographically // greater. static bool compareSeq(string S, int x, int y, int n) { for (int i = 0; i < n; i++) { if (S[x] < S[y]) return false; else if (S[x] > S[y]) return true; x = (x + 1) % n; y = (y + 1) % n; } return true; } // Function to find starting index // of lexicographically smallest sequence static int smallestSequence(string S, int n) { int index = 0; for (int i = 1; i < n; i++) // if new sequence is smaller if (compareSeq(S, index, i, n)) // change index of current min index = i; return index; } // Function to print lexicographically // smallest sequence static void printSmallestSequence(string str, int n) { // char[] S=str.toCharArray(); int starting_index = smallestSequence(str, n); for (int i = 0; i < n; i++) Console.Write(str[(starting_index + i) % n]); } // driver code public static void Main() { string S = "DCACBCAA"; int n = 8; printSmallestSequence(S, n); } } // This code is contributed by vt_m.
PHP
<?php // PHP 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. function compareSeq($S, $x, $y, $n) { for($i = 0; $i < $n; $i++) { if ($S[$x] < $S[$y]) return false; else if ($S[$x] > $S[$y]) return true; $x = ($x + 1) % $n; $y = ($y + 1) % $n; } return true; } // Function to find starting index // of lexicographically smallest // sequence function smallestSequence($S, $n) { $index = 0; for ( $i = 1; $i < $n; $i++) // if new sequence is smaller if (compareSeq($S, $index, $i, $n)) // change index of current min $index = $i; return $index; } // Function to print lexicographically // smallest sequence function printSmallestSequence($S, $n) { $starting_index = smallestSequence($S, $n); for ($i = 0; $i < $n; $i++) echo $S[($starting_index + $i) % $n]; } // Driver Code $S= "DCACBCAA"; $n = 8; printSmallestSequence($S, $n); // This code is contributed by Ajit. ?>
Javascript
<script> // Javascript 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. function compareSeq(S,x,y,n) { for (let i = 0; i < n; i++) { if (S[x] < S[y]) return false; else if (S[x] > S[y]) return true; x = (x + 1) % n; y = (y + 1) % n; } return true; } // Function to find starting index // of lexicographically smallest sequence function smallestSequence(S,n) { let index = 0; for (let i = 1; i < n; i++) // if new sequence is smaller if (compareSeq(S, index, i, n)) // change index of current min index = i; return index; } // Function to print lexicographically // smallest sequence function printSmallestSequence(str,n) { let S = str.split(""); let starting_index = smallestSequence(S, n); for (let i = 0; i < n; i++) document.write(S[(starting_index + i) % n]); } // driver code let S = "DCACBCAA"; let n = 8; printSmallestSequence(S, n); // This code is contributed by avanitrachhadiya2155 </script>
AADCACBC
Complejidad de tiempo: O(n^2)
Espacio auxiliar: O(1)
Este artículo es una contribución de Pratik Chhajer . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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