给定一个数组moves[]包含前n个自然数的排列，该数组的每个元素都代表一个移动，即每个元素都显示一个索引，元素在每个步骤后的位置。现在，按照这些步骤，我们需要告诉数组[1..n]返回[1..n]的步骤有多少。一个步骤定义如下，在一个步骤之后，每个元素将被移动到由moves数组索引定义的位置。 例如：
null
Input : moves[] = [4, 5, 1, 3, 2]Output : 6Explanation:We need to consider an array of first 5 natural numbers, i.e., arr[] = {1, 2, 3, 4, 5} assize of moves[] is 5.Now we one by one move elements of arr[] using given moves. moves[] = [4, 5, 1, 3, 2] arr[] = [1, 2, 3, 4, 5] In step 1, we move 1 to position 4, 2 to position5, 3 to position 1, 4 to position 3 and 5 to position 2.After step 1: arr[] = [3, 5, 4, 1, 2]In step 2, we move 3 to position 4, 5 to position5, 4 to position 1, 1 to position 3 and 2 to position 2After step 2: arr[] = [4, 2, 1, 3, 5]After step 3: arr[] = [1, 5, 3, 4, 2]After step 4: arr[] = [3, 2, 4, 1, 5]After step 5: arr[] = [4, 5, 1, 3, 2]After step 6: arr[] = [1, 2, 3, 4, 5]So we can reach to initial array in 6 steps, this is the minimum steps for reverting to the initial configuration of array.Input : moves[] = {3, 2, 1}Output : 2
我们可以通过观察形成的序列中的模式来解决这个问题。移动数组的一组特定元素构成一个循环。如上所述，示例[4,1,3]和[5,2]是两个这样的集合。这两个周期是独立的。
[4, 1, 3] causes [1, 3, 4] -> [3, 4, 1] -> [4, 1, 3] -> [1, 3, 4] -> [3, 4, 1] -> [4, 1, 3] -> [1, 3, 4][5, 2] causes [2, 5] -> [5, 2] -> [2, 5] -> [5, 2] -> [2, 5] -> [5, 2] -> [2, 5]
我们可以从上面的变化看出，长度为3的循环需要3个步骤才能达到相同的状态，长度为2的循环需要2个步骤才能达到相同的状态。一般来说，如果一个循环的长度为N，那么经过N步之后，我们可以达到相同的状态。 现在，如果给定的移动数组只有一个周期，那么我们可以达到起始状态，移动的数量等于数组中所有元素的数量，但是如果它有超过1个周期，那么所有元素都会独立地移动，并且所有元素都会在x个移动次数之后达到起始状态，其中x应该可以被所有周期长度整除，因为分割所有周期长度的最小x是它们的LCM，我们仍在寻找所有周期长度的LCM。 循环长度可以通过逐个访问元素来找到，从我们要移动的任何元素开始，直到我们到达起始元素，我们将计算这个过程中的元素数量，这将是相应的循环长度。
Below is example of cycles found for some moves arrays,[2, 3, 1, 5, 4] -> [2, 3, 1] and [5, 4][1, 2, 3, 4, 5] -> [1] [2] [3] [4] [5][2, 3, 4, 1, 5] -> [2, 3, 4, 1] and [5]
唯一剩下的就是计算这些长度的LCM，可以使用GCD轻松计算。
C++
// C++ program to get minimum steps to return to // initial array with specified movement #include <bits/stdc++.h> using namespace std; // Utility method to get lcm of a and b int lcm( int a, int b) { return (a * b) / __gcd(a, b); } // Method returns minimum number of steps to // return to initial array int getMinStepsToSort( int moves[], int N) { // initially all cells are unvisited bool visit[N]; memset (visit, false , sizeof (visit)); // looping over all elements to get // various cycle int steps = 1; for ( int i = 0; i < N; i++) { // if already visited, that means it // was a part of some cycle if (visit[i]) continue ; int cycleLen = 0; // Looping among cycle elements, -1 is // for converting value to 0-index based for ( int j = i; !visit[j]; j = moves[j] - 1) { cycleLen++; visit[j] = true ; } // Take the lcm of current result and // new cycle length steps = lcm(steps, cycleLen); } return steps; } // Driver code to test above methods int main() { int moves[] = { 4, 5, 1, 3, 2 }; int N = sizeof (moves) / sizeof ( int ); cout << getMinStepsToSort(moves, N); return 0; } |
JAVA
// Java program to get minimum steps to // return to initial array with specified // movement import java.util.Arrays; class GFG { // Recursive function to return gcd // of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0 || b == 0 ) return 0 ; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Utility method to get lcm of a and b static int lcm( int a, int b) { return (a * b) / __gcd(a, b); } // Method returns minimum number of steps // to return to initial array static int getMinStepsToSort( int moves[], int N) { // initially all cells are unvisited boolean visit[] = new boolean [N]; Arrays.fill(visit, false ); // looping over all elements to get // various cycle int steps = 1 ; for ( int i = 0 ; i < N; i++) { // if already visited, that // means it was a part of some // cycle if (visit[i]) continue ; int cycleLen = 0 ; // Looping among cycle elements, // -1 is for converting value to // 0-index based for ( int j = i; !visit[j]; j = moves[j] - 1 ) { cycleLen++; visit[j] = true ; } // Take the lcm of current result // and new cycle length steps = lcm(steps, cycleLen); } return steps; } // Driver code public static void main(String arg[]) { int moves[] = { 4 , 5 , 1 , 3 , 2 }; int N = moves.length; System.out.print(getMinStepsToSort( moves, N)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to get # minimum steps to return to # initial array with # specified movement # Recursive function to # return gcd of a and b def __gcd(a, b): # Everything divides 0 if (a = = 0 or b = = 0 ): return 0 # base case if (a = = b): return a # a is greater if (a > b): return __gcd(a - b, b) return __gcd(a, b - a) # Utility method to # get lcm of a and b def lcm(a, b): return (a * b) / / __gcd(a, b) # Method returns minimum # number of steps to # return to initial array def getMinStepsToSort(moves, N): # initially all cells are unvisited visit = [ False for i in range (N + 1 )] # looping over all # elements to get # various cycle steps = 1 for i in range (N): # if already visited, # that means it # was a part of some cycle if (visit[i]): continue cycleLen = 0 # Looping among cycle # elements, -1 is # for converting value # to 0-index based j = i while ( not visit[j]): cycleLen + = 1 visit[j] = True j = moves[j] - 1 # Take the lcm of # current result and # new cycle length steps = lcm(steps, cycleLen) return steps # Driver code moves = [ 4 , 5 , 1 , 3 , 2 ] N = len (moves) print (getMinStepsToSort(moves, N)) # This code is contributed # by Anant Agarwal. |
C#
// C# program to get minimum steps to return // to initial array with specified movement using System; class GFG { // Recursive function to return gcd // of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Utility method to get lcm of a and b static int lcm( int a, int b) { return (a * b) / __gcd(a, b); } // Method returns minimum number of steps // to return to initial array static int getMinStepsToSort( int [] moves, int N) { // initially all cells are unvisited bool [] visit = new bool [N]; // looping over all elements to get // various cycle int steps = 1; for ( int i = 0; i < N; i++) { // if already visited, that // means it was a part of some cycle if (visit[i]) continue ; int cycleLen = 0; // Looping among cycle elements, // -1 is for converting value to // 0-index based for ( int j = i; !visit[j]; j = moves[j] - 1) { cycleLen++; visit[j] = true ; } // Take the lcm of current result // and new cycle length steps = lcm(steps, cycleLen); } return steps; } // Driver code public static void Main() { int [] moves = { 4, 5, 1, 3, 2 }; int N = moves.Length; Console.WriteLine(getMinStepsToSort(moves, N)); } } // This code is contributed by vt_m. |
Javascript
<script> // Javascript program to get minimum steps to return // to initial array with specified movement // Recursive function to return gcd // of a and b function __gcd(a, b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Utility method to get lcm of a and b function lcm(a, b) { return parseInt((a * b) / __gcd(a, b), 10); } // Method returns minimum number of steps // to return to initial array function getMinStepsToSort(moves, N) { // initially all cells are unvisited let visit = new Array(N); visit.fill( false ); // looping over all elements to get // various cycle let steps = 1; for (let i = 0; i < N; i++) { // if already visited, that // means it was a part of some cycle if (visit[i]) continue ; let cycleLen = 0; // Looping among cycle elements, // -1 is for converting value to // 0-index based for (let j = i; !visit[j]; j = moves[j] - 1) { cycleLen++; visit[j] = true ; } // Take the lcm of current result // and new cycle length steps = lcm(steps, cycleLen); } return steps; } let moves = [ 4, 5, 1, 3, 2 ]; let N = moves.length; document.write(getMinStepsToSort(moves, N)); </script> |
输出：
6
本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
