力扣第89题 格雷编码

题目描述

格雷编码序列是一个二进制数字序列，其中的每两个相邻的数字只有一个二进制位不同。给定一个整数 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. 递归法
2. 数学公式法

方法 1：递归法（构建反射法）

递归的核心思想是：

1. 通过已有的 $n$ 位的格雷编码序列，构建 $n+1$ 位的格雷编码序列。
2. 假设已有 $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\oplus (k>>1)$$
其中，$k$ 是当前的数字，$k>>1$ 是 $k$ 右移一位，$k\oplus (k>>1)$ 是 $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$ 位。
• 每次扩展时，通过反射法创建新的序列：
  • 将已有的序列复制到前半部分。
  • 将每个数值在前面加上 1，并将该部分的顺序反转，加入到后半部分。

2. 数学公式法实现

• 通过公式 $G(k)=k\oplus (k>>1)$ 来计算每个数字的格雷编码。
• 通过位运算，我们可以在 $O(1)$ 的时间内生成每个数字的格雷编码。

---

时间与空间复杂度

时间复杂度

• 对于递归法：生成每一位的格雷编码序列时，需要 $O(2^n)$ 的时间，因此时间复杂度是 $O(2^n)$。
• 对于数学公式法：直接计算每个数字的格雷编码，因此时间复杂度是 $O(2^n)$。

空间复杂度

• 对于两种方法：需要存储生成的格雷编码序列，空间复杂度是 $O(2^n)$。

---

测试用例

示例 1：

输入：

n = 2

输出：

[0, 1, 3, 2]

示例 2：

输入：

n = 3

输出：

[0, 1, 3, 2, 6, 7, 5, 4]