还原排列的最少操作步数【LC1806】
You are given an even integer n. You initially have a permutation perm of size n where perm[i] == i (0-indexed).
In one operation, you will create a new array arr, and for each i:
- If i % 2 == 0, then arr[i] = perm[i / 2].
- If i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2].
You will then assign arr to perm.
Return the minimum non-zero number of operations you need to perform on perm to return the permutation to its initial value.
数学就算了 不要为难自己
- 思路：按照题意进行变换，直至数组变为原始数组，记录变换次数
- 实现
class Solution { public int reinitializePermutation(int n) { int[] perm = new int[n]; int[] arr = new int[n]; for (int i = 0; i < n; i++) perm[i] = i; for (int i = 0; i < n; i++){ if (i % 2 == 0){ arr[i] = perm[i / 2]; }else{ arr[i] = perm[n / 2 + (i - 1) / 2]; } } int count = 1; while (!Arrays.equals(perm, arr)){ int[] tmp = new int[n]; for (int i = 0; i < n; i++){ if (i % 2 == 0){ tmp[i] = arr[i / 2]; }else{ tmp[i] = arr[n / 2 + (i - 1) / 2]; } } for (int i = 0; i < n; i++) arr[i] = tmp[i]; count++; } return count; } }
。复杂度
- 时间复杂度：O ( n 2 )
- 空间复杂度：O ( n )
- 好看的代码
class Solution { public int reinitializePermutation(int n) { int[] prem = new int[n], arr = new int[n]; for (int i = 0; i < n; i++) prem[i] = i; int i, step = 1; while (true) { for (i = 0; i < n; i++) arr[i] = i % 2 == 0 ? prem[i / 2] : prem[(n - 1 + i) / 2]; for (i = 0; i < n && arr[i] == i; i++); if (i == n) return step; for (i = 0; i < n; i++) prem[i] = arr[i]; step++; } } } 作者：Tizzi 链接：https://leetcode.cn/problems/minimum-number-of-operations-to-reinitialize-a-permutation/solutions/2052353/liang-chong-jie-fa-mo-ni-mo-ni-you-hua-b-2ijm/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
