Medium

题目描述

给定两个整数 n 和 start。你需要返回 (0,1,2,...,2^n-1) 的任意一个排列 p，使得：

  • p[0] = start
  • p[i] 和 p[i+1] 在二进制表示中只有一位不同
  • p[0] 和 p[2^n-1] 在二进制表示中也只有一位不同

示例 1：

输入：n = 2, start = 3
输出：[3,2,0,1]
解释：排列的二进制表示是 (11,10,00,01)。
所有相邻元素都只相差一位。另一个有效排列是 [3,1,0,2]

示例 2：

输入：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：排列的二进制表示是 (010,110,111,101,100,000,001,011)。

约束：

  • 1 <= n <= 16
  • 0 <= start < 2^n

提示：

  • 使用格雷码生成 n 位序列
  • 旋转序列，使其第一个元素为 start

解题思路

这道题要求找到一个从 0 到 2^n-1 的排列，使得相邻元素（包括首尾相接）的二进制表示只相差一位。这正是**格雷码（Gray Code）**的定义。

解题思路：

  1. 格雷码生成：格雷码是一种特殊的二进制编码，其中相邻两个数的二进制表示只有一位不同。n位格雷码可以通过递归生成：

    • 0位格雷码：[0]
    • n位格雷码 = [0+前n-1位格雷码] + [1+前n-1位格雷码的逆序]

  2. 数学公式：第i个格雷码可以用公式直接计算：gray[i] = i ^ (i >> 1)

  3. 旋转到start：生成完整的格雷码序列后，找到start在序列中的位置，然后将序列旋转，使start成为第一个元素。

算法步骤：

  1. 使用公式生成n位格雷码序列
  2. 找到start在序列中的索引位置
  3. 将序列从该位置开始重新排列，形成以start开头的循环排列

时间复杂度为O(2^n)，空间复杂度为O(2^n)，这是最优解法。

代码实现

class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> result;
        int size = 1 << n; // 2^n
        
        // 生成格雷码序列
        for (int i = 0; i < size; i++) {
            result.push_back(i ^ (i >> 1));
        }
        
        // 找到start在格雷码序列中的位置
        int startIndex = 0;
        for (int i = 0; i < size; i++) {
            if (result[i] == start) {
                startIndex = i;
                break;
            }
        }
        
        // 旋转序列，使start成为第一个元素
        vector<int> rotated;
        for (int i = 0; i < size; i++) {
            rotated.push_back(result[(startIndex + i) % size]);
        }
        
        return rotated;
    }
};

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        size = 1 << n  # 2^n
        
        # 生成格雷码序列
        gray_code = []
        for i in range(size):
            gray_code.append(i ^ (i >> 1))
        
        # 找到start在格雷码序列中的位置
        start_index = gray_code.index(start)
        
        # 旋转序列，使start成为第一个元素
        return gray_code[start_index:] + gray_code[:start_index]

public class Solution {
    public IList<int> CircularPermutation(int n, int start) {
        int size = 1 << n; // 2^n
        List<int> result = new List<int>();
        
        // 生成格雷码序列
        for (int i = 0; i < size; i++) {
            result.Add(i ^ (i >> 1));
        }
        
        // 找到start在格雷码序列中的位置
        int startIndex = result.IndexOf(start);
        
        // 旋转序列，使start成为第一个元素
        List<int> rotated = new List<int>();
        for (int i = 0; i < size; i++) {
            rotated.Add(result[(startIndex + i) % size]);
        }
        
        return rotated;
    }
}

/**
 * @param {number} n
 * @param {number} start
 * @return {number[]}
 */
var circularPermutation = function(n, start) {
    const size = 1 << n; // 2^n
    const grayCode = [];
    
    // 生成格雷码序列
    for (let i = 0; i < size; i++) {
        grayCode.push(i ^ (i >> 1));
    }
    
    // 找到start在格雷码序列中的位置
    const startIndex = grayCode.indexOf(start);
    
    // 旋转序列，使start成为第一个元素
    return grayCode.slice(startIndex).concat(grayCode.slice(0, startIndex));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(2^n)需要生成2^n个格雷码，查找start位置需要O(2^n)时间
空间复杂度O(2^n)存储格雷码序列需要O(2^n)空间