分析

• 本题的考点：递推构造。

• 按照如下图方式进行构造即可：

• 其实这是一个递推的过程，当得到n-1的结果后，将整个结果沿着对称轴翻转，然后对称轴上方的数据后面补0，下面的补1，即可得到n的结果。

代码

• C++

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res(1, 0);
        while (n--) {
            for (int i = res.size() - 1; i >= 0; i--) {
                res[i] *= 2;
                res.push_back(res[i] + 1);
            }
        }
        return res;
    }
};

• Java

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        while (n-- != 0) {
            for (int i = res.size() - 1; i >= 0; i--) {
                res.set(i, res.get(i) * 2);
                res.add(res.get(i) + 1);
            }
        }
        return res;
    }
}

时空复杂度分析

• 时间复杂度：$O(2^n)$。

• 空间复杂度：考虑结果的存储 $O(2^n)$。