循环码排列 图解题解
这道题到底在问什么
- 输入
- n = 2, start = 3
- 输出
- [3, 2, 0, 1]
- 输入
- 本节演示 n = 3, start = 2
- 输出
- [2, 6, 7, 5, 4, 0, 1, 3]
先想最直接的笨办法
舞台上是即将生成的灰码序列 g,一共 8 个槽位,现在都是灰的、还没算。规则只有一条公式:第 i 个数等于 i 异或上「i 右移一位」。从 i=0 开始,一个一个往右填。（动画第 4 步）
最优解：一步一步想明白
- 3记牢两步:第一步用公式造灰码序列,第二步把序列旋转到 start 开头。下面每帧都在套这两步。
- 4舞台上是即将生成的灰码序列 g,一共 8 个槽位,现在都是灰的、还没算。规则只有一条公式:第 i 个数等于 i 异或上「i 右移一位」。从 i=0 开始,一个一个往右填。
- 5算第 0 个:i=0(二进制 000)右移一位得 0(二进制 000),两者异或得 0(二进制 000)。它是序列开头,固定从 0 出发。
- 6算第 1 个:i=1(二进制 001)右移一位得 0(二进制 000),两者异或得 1(二进制 001)。它和上一个 g[0] = 0(二进制 000)对比,二进制 001 与 000 恰好只有一位不同,相邻差一位成立。
- 7算第 2 个:i=2(二进制 010)右移一位得 1(二进制 001),两者异或得 3(二进制 011)。它和上一个 g[1] = 1(二进制 001)对比,二进制 011 与 001 恰好只有一位不同,相邻差一位成立。
- 8算第 3 个:i=3(二进制 011)右移一位得 1(二进制 001),两者异或得 2(二进制 010)。它和上一个 g[2] = 3(二进制 011)对比,二进制 010 与 011 恰好只有一位不同,相邻差一位成立。
- 9算第 4 个:i=4(二进制 100)右移一位得 2(二进制 010),两者异或得 6(二进制 110)。它和上一个 g[3] = 2(二进制 010)对比,二进制 110 与 010 恰好只有一位不同,相邻差一位成立。
- 10算第 5 个:i=5(二进制 101)右移一位得 2(二进制 010),两者异或得 7(二进制 111)。它和上一个 g[4] = 6(二进制 110)对比,二进制 111 与 110 恰好只有一位不同,相邻差一位成立。
- 11算第 6 个:i=6(二进制 110)右移一位得 3(二进制 011),两者异或得 5(二进制 101)。它和上一个 g[5] = 7(二进制 111)对比,二进制 101 与 111 恰好只有一位不同,相邻差一位成立。
- 12算第 7 个:i=7(二进制 111)右移一位得 3(二进制 011),两者异或得 4(二进制 100)。它和上一个 g[6] = 5(二进制 101)对比,二进制 100 与 101 恰好只有一位不同,相邻差一位成立。
- 13序列造好了:[0, 1, 3, 2, 6, 7, 5, 4]。它天然满足相邻只差一位,可它是从 0 开头的,而题目要 start=2 打头。先在 g 里找到 2 的位置,它在下标 3(绿色标出)。下一步就把序列从这里旋转过去。
- 14把序列在下标 3 处切成两段:绿色是从 start 开始到末尾的前段 [2, 6, 7, 5, 4],蓝色是开头到 start 之前的后段 [0, 1, 3]。旋转就是把绿色段搬到最前面、蓝色段接到它后面。
- 15先把绿色前段 [2, 6, 7, 5, 4] 整段搬到最前面。这样第 0 个数就是 2,正好等于 start=2,第一个约束达成。后面还差把蓝色段接上。
- 16再把蓝色后段 [0, 1, 3] 接到末尾(绿色高亮)。拼出来完整排列 p = [2, 6, 7, 5, 4, 0, 1, 3]。它就是 g[3:] 接上 g[:3] 的结果。接下来逐对检查:相邻是不是真的只差一位。
- 17检查第 0 和第 1 这对:2(二进制 010)和 6(二进制 110),异或结果 100,里面只有一个 1,落在第 2 位,说明只翻了一个比特,相邻差一位成立。
- 18检查第 1 和第 2 这对:6(二进制 110)和 7(二进制 111),异或结果 001,里面只有一个 1,落在第 0 位,说明只翻了一个比特,相邻差一位成立。
- 19检查第 2 和第 3 这对:7(二进制 111)和 5(二进制 101),异或结果 010,里面只有一个 1,落在第 1 位,说明只翻了一个比特,相邻差一位成立。
- 20检查第 3 和第 4 这对:5(二进制 101)和 4(二进制 100),异或结果 001,里面只有一个 1,落在第 0 位,说明只翻了一个比特,相邻差一位成立。
- 21检查第 4 和第 5 这对:4(二进制 100)和 0(二进制 000),异或结果 100,里面只有一个 1,落在第 2 位,说明只翻了一个比特,相邻差一位成立。
- 22检查第 5 和第 6 这对:0(二进制 000)和 1(二进制 001),异或结果 001,里面只有一个 1,落在第 0 位,说明只翻了一个比特,相邻差一位成立。
- 23检查第 6 和第 7 这对:1(二进制 001)和 3(二进制 011),异或结果 010,里面只有一个 1,落在第 1 位,说明只翻了一个比特,相邻差一位成立。
- 24最后看首尾这一对(环形):末尾 3(二进制 011)和开头 2(二进制 010),异或得 001,只有第 0 位不同。环也只差一位,第三个约束达成。8 个数全部检验通过。
⚠️ 容易写错的地方
✗ 错：格雷码公式记成 i 异或 (i 左移 1) 或漏掉右移
✓ 对：务必是 i 异或 (i 右移 1)
只有右移一位的反射格雷码才保证相邻整数 i 与 i+1 的码字恰好翻一个比特;左移或不移都会一次翻多位
✗ 错：找到 start 后忘了旋转,序列仍从 0 开头
✓ 对：在 g 里定位 start 的下标 j,旋转成 g[j:] 接 g[:j]
题目硬性要求 p[0] = start;不旋转的话 p[0] 永远是 0,直接不合法
✗ 错：担心旋转后首尾不再差一位,去特殊拼接
✓ 对：不用管,旋转一个环不破坏环形相邻
原始格雷码本就首尾差一位(是个环),把环转一下,任意相邻关系包括新首尾都原样保留
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def circularPermutation(self, n: int, start: int) -> List[int]:
g = [i ^ (i >> 1) for i in range(1 << n)]
j = g.index(start)
return g[j:] + g[:j]C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<int> circularPermutation(int n, int start) {
int g[1 << n];
int j = 0;
for (int i = 0; i < 1 << n; ++i) {
g[i] = i ^ (i >> 1);
if (g[i] == start) {
j = i;
}
}
vector<int> ans;
for (int i = j; i < j + (1 << n); ++i) {
ans.push_back(g[i % (1 << n)]);
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public List<Integer> circularPermutation(int n, int start) {
int[] g = new int[1 << n];
int j = 0;
for (int i = 0; i < 1 << n; ++i) {
g[i] = i ^ (i >> 1);
if (g[i] == start) {
j = i;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = j; i < j + (1 << n); ++i) {
ans.add(g[i % (1 << n)]);
}
return ans;
}
}复杂度
时间
O(2 的 n 次方)
设 N = 2 的 n 次方,即输出长度。生成灰码序列扫一遍 N、定位 start 最多扫一遍 N、旋转拼接再走一遍 N,三段都是线性,合起来还是 O(N)
空间
O(2 的 n 次方)
要存一条长度 N 的灰码序列,答案本身也有 N 个元素。按峰值占用算是 O(N);若不显式建数组、改用 p[i] = (i 异或 i 右移 1) 异或 start 直接公式输出,可降到除输出外 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 循环码排列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 i 异或 (i 右移 1) 能保证相邻只差一位?+
这是反射二进制格雷码的定义性质。把整数 i 右移一位再和自身异或,得到的码字序列里,任意相邻的 i 和 i+1 恰好只有一个比特不同。可以从反射构造法理解:n 位格雷码是把 n 减 1 位的格雷码正序前面补 0、再倒序前面补 1 拼起来,正反交界处和补位都只动一位,所以全程相邻差一位,而且首尾也差一位,天然成环。
旋转之后,首尾为什么仍然只差一位?+
因为原始格雷码序列本身就是一个环:g[0]=0 和 g[最后一个] 也只差一位。把一个环从任意位置切开再首尾相接,等于把这个环转了个角度,所有相邻关系包括新的首尾对都原封不动,所以旋转后照样满足首尾差一位,不需要任何额外处理。
有没有不显式建数组的写法?+
有。可以直接用公式 p[i] = (i 异或 (i 右移 1)) 异或 start 一次性输出,它同样是一个合法排列且 p[0] 等于 start,额外空间除输出外是 O(1)。本解之所以选「造序列再旋转」,是因为它把过程拆得很直观、也便于和样例输出对照;两种写法都对,只是给出的具体排列顺序可能不同。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 循环码排列 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。