题目描述
格雷编码序列是一个二进制数字序列,其中的每两个相邻的数字只有一个二进制位不同。给定一个整数 n
,表示格雷编码的位数,要求返回 n
位的格雷编码序列。
示例 1
输入:
n = 2
输出:
[0, 1, 3, 2]
解释:
- 对于
n = 2
,对应的格雷编码序列为[00, 01, 11, 10]
,它们的十进制表示为[0, 1, 3, 2]
。
示例 2
输入:
n = 3
输出:
[0, 1, 3, 2, 6, 7, 5, 4]
解释:
- 对于
n = 3
,对应的格雷编码序列为[000, 001, 011, 010, 110, 111, 101, 100]
,它们的十进制表示为[0, 1, 3, 2, 6, 7, 5, 4]
。
解题思路
格雷编码序列的生成有两种常见方法:
- 递归法
- 数学公式法
方法 1:递归法(构建反射法)
递归的核心思想是:
- 通过已有的 n n n 位的格雷编码序列,构建 n + 1 n+1 n+1 位的格雷编码序列。
- 假设已有 n n n 位的格雷编码序列为
G(n)
,我们可以通过以下方法得到G(n+1)
:G(n+1)
的前半部分是G(n)
本身。G(n+1)
的后半部分是G(n)
的每个元素前面加上一个1
,并且反转原序列的顺序。
举个例子:
- 对于
n = 1
,格雷编码序列是[0, 1]
。 - 对于
n = 2
,格雷编码序列是[00, 01, 11, 10]
。
方法 2:数学公式法
格雷编码的数学公式为:
G ( k ) = k ⊕ ( k > > 1 ) G(k) = k \oplus (k >> 1) G(k)=k⊕(k>>1)
其中, k k k 是当前的数字, k > > 1 k >> 1 k>>1 是 k k k 右移一位, k ⊕ ( k > > 1 ) k \oplus (k >> 1) k⊕(k>>1) 是 k k k 与右移后的 k k k 进行按位异或操作。
使用该公式可以快速生成格雷编码序列。
代码实现
方法 1:递归法
#include <stdio.h>
#include <stdlib.h>int* grayCode(int n, int* returnSize) {*returnSize = 1 << n; // 返回的序列长度为 2^nint* result = (int*)malloc(sizeof(int) * (*returnSize));// 初始的 0 位格雷编码result[0] = 0;for (int i = 1; i <= n; i++) {int size = 1 << (i - 1); // 当前格雷编码的长度for (int j = size - 1; j >= 0; j--) {result[size + j] = result[j] | (1 << (i - 1)); // 更新后半部分}}return result;
}void printArray(int* arr, int size) {for (int i = 0; i < size; i++) {printf("%d", arr[i]);if (i < size - 1) printf(", ");}printf("\n");
}int main() {int n = 3;int returnSize = 0;int* result = grayCode(n, &returnSize);printArray(result, returnSize);free(result);return 0;
}
方法 2:数学公式法
#include <stdio.h>
#include <stdlib.h>int* grayCode(int n, int* returnSize) {*returnSize = 1 << n; // 返回的序列长度为 2^nint* result = (int*)malloc(sizeof(int) * (*returnSize));for (int i = 0; i < *returnSize; i++) {result[i] = i ^ (i >> 1); // 使用公式生成格雷编码}return result;
}void printArray(int* arr, int size) {for (int i = 0; i < size; i++) {printf("%d", arr[i]);if (i < size - 1) printf(", ");}printf("\n");
}int main() {int n = 3;int returnSize = 0;int* result = grayCode(n, &returnSize);printArray(result, returnSize);free(result);return 0;
}
代码详解
1. 递归法实现
- 我们从最简单的格雷编码
[0]
开始,逐步扩展到 n n n 位。 - 每次扩展时,通过反射法创建新的序列:
- 将已有的序列复制到前半部分。
- 将每个数值在前面加上
1
,并将该部分的顺序反转,加入到后半部分。
2. 数学公式法实现
- 通过公式 G ( k ) = k ⊕ ( k > > 1 ) G(k) = k \oplus (k >> 1) G(k)=k⊕(k>>1) 来计算每个数字的格雷编码。
- 通过位运算,我们可以在 O ( 1 ) O(1) O(1) 的时间内生成每个数字的格雷编码。
时间与空间复杂度
时间复杂度
- 对于递归法:生成每一位的格雷编码序列时,需要 O ( 2 n ) O(2^n) O(2n) 的时间,因此时间复杂度是 O ( 2 n ) O(2^n) O(2n)。
- 对于数学公式法:直接计算每个数字的格雷编码,因此时间复杂度是 O ( 2 n ) O(2^n) O(2n)。
空间复杂度
- 对于两种方法:需要存储生成的格雷编码序列,空间复杂度是 O ( 2 n ) O(2^n) O(2n)。
测试用例
示例 1:
输入:
n = 2
输出:
[0, 1, 3, 2]
示例 2:
输入:
n = 3
输出:
[0, 1, 3, 2, 6, 7, 5, 4]