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
, thenarr[i] = perm[i / 2]
. - If
i % 2 == 1
, thenarr[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.
Example 1:
Input: n = 2 Output: 1 Explanation: prem = [0,1] initially. After the 1st operation, prem = [0,1] So it takes only 1 operation.
Example 2:
Input: n = 4 Output: 2 Explanation: prem = [0,1,2,3] initially. After the 1st operation, prem = [0,2,1,3] After the 2nd operation, prem = [0,1,2,3] So it takes only 2 operations.
Example 3:
Input: n = 6 Output: 4
Constraints:
2 <= n <= 1000
n
is even.
Solution: Brute Force / Simulation
Time complexity: O(n2) ?
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int reinitializePermutation(int n) { vector<int> perm(n); vector<int> arr(n); for (int i = 0; i < n; ++i) perm[i] = i; int ans = 0; bool flag = true; while (flag && ++ans) { flag = false; for (int i = 0; i < n; ++i) { arr[i] = i & 1 ? perm[n / 2 + (i - 1) / 2] : perm[i / 2]; flag |= arr[i] != i; } swap(perm, arr); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment