1806.还原排列的最少操作步数.md

1806.还原排列的最少操作步数

/*
 * @lc app=leetcode.cn id=1806 lang=typescript
 *
 * [1806] 还原排列的最少操作步数
 */

// @lc code=start
function reinitializePermutation(n: number): number {}

// @lc code=end

解法 1: 直接模拟

function reinitializePermutation(n: number): number {
  const a = [[...new Array(n).keys()], [...new Array(n).keys()]]
  let res = 0
  while (1) {
    res++
    let flag = true,
      x = res & 1,
      y = x ^ 1
    for (let i = 0; i < n; i++) {
      a[y][i] = i & 1 ? a[x][n / 2 + (i - 1) / 2] : a[x][i / 2]
      if (a[y][i] !== i) flag = false
    }
    if (flag) return res
  }
}

解法 2: 计算单个位置的变化

根据题意，我们可以推导出当前位置 i 进行一次操作之后，会出现的下一个位置 j

具体的，假设下一个位置 j 为偶数，则 $i=j/2$,可以解出 $j=2i$；如果 j 为奇数，则 $i=n/2+(j-1)/2$，可以解出 $j=2i-(n-1)$

总结起来可得 $j=(2*i)%(n-1)$,于是我们可以通过模拟一个位置的变化，直到最终这个位置回到初始的位置，既为找到答案

后面想了下，一开始直接使用 n-2 作为开始位置去枚举，结果可以通过，但为什么从 n-2 开始一定是正确的，却没想到要怎么证明？

function reinitializePermutation(n: number): number {
  let i = n - 2,
    res = 0,
    MOD = n - 1
  while (1) {
    res++
    i = (2 * i) % MOD
    if (i === n - 2) return res
  }
  return -1
}

Case

test.each([
  { input: { n: 2 }, output: 1 },
  { input: { n: 4 }, output: 2 },
  { input: { n: 6 }, output: 4 },
])('input: n = $input.n', ({ input: { n } output }) => {
  expect(reinitializePermutation(n)).toEqual(output)
})