1238. 循环码排列

题目链接：1238. 循环码排列

方法：格雷码

解题思路

令 \(N = 2^n-1\)，将 \(i = 0, ... , N，\) 分别转换为其对应的格雷码，用 \(g\) 数组存储，即 \(g[i]\) 表示 \(i\) 对应的格雷码的十进制的值。由于题目中 \(start\) 表示的是格雷码的十进制值，且返回的为格雷码的十进制值的数组，在 \(g\) 数组中找 \(g[j] = start\)，那么 \(ans = [g[j], ..., g[N-1], ..., g[0], ... ,g[j-1]]\)。

代码

class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        int N = 1 << n;
        vector<int> g(N);
        int j;
        for (int i = 0; i < N; i ++ ) {
            g[i] = i ^ (i >> 1); // i的二进制格雷码对应的十进制的值
            // 记下start在g数组中的位置，那么ans = [g[j], ... , g[N - 1], g[0], ... , g[j - 1]]
            if (g[i] == start) j = i; 
        }
        vector<int> ans;
        for (int i = j; i < N + j; i ++ ) {
            ans.push_back(g[i % N]);
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：O(\(2^n\))；
空间复杂度：O(\(2^n\))。