0089. 格雷编码【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 公式法

1. 📝 题目描述

• leetcode

n 位格雷码序列 是一个由 2^n 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2^n - 1] 内（含 0 和 2^n - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n，返回任一有效的 n 位格雷码序列。

---

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10]。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01]。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

输入：n = 1
输出：[0,1]

---

提示：

• 1 <= n <= 16

2. 🎯 s.1 - 公式法

c

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* grayCode(int n, int* returnSize) {
    *returnSize = 1 << n;
    int* result = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < *returnSize; i++)
        result[i] = i ^ (i >> 1); // 格雷编码公式
    return result;
}

js

/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function (n) {
  const result = []
  for (let i = 0; i < 1 << n; i++) result.push(i ^ (i >> 1)) // 格雷编码公式
  return result
}

py

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [i ^ (i >> 1) for i in range(1 << n)]  # 格雷编码公式

• 时间复杂度：$O(2^n)$，生成 $2^n$ 个格雷编码
• 空间复杂度：$O(1)$，不计输出数组，只使用常数额外空间

算法思路：

• 格雷编码公式：$G(i)=i\oplus (i>>1)$，即将整数 i 与其右移一位的结果异或
• 该公式保证相邻两个编码恰好只有一位不同
• 遍历 $[0,2^n)$，对每个 i 应用公式即可