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.
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>
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