二进制字典序构造第N个数解题过程详解
首先明确核心思路：本题本质上就是按照二进制字典序，构造出第N个恰好包含k个1的数。关键在于灵活运用组合数进行决策。下面我们一步步拆解。
一、前置准备：预处理组合数表
在开始算法主逻辑之前，提前计算好组合数表至关重要——它相当于整个算法的“弹药库”。后续每一步决策都可以直接查表获取方案数，无需实时计算，极大提升效率。
- 组合数的定义：
C(i, j)表示从 i 个位置中选 j 个位置放1的总方案数，正好对应“二进制数有j个1”的数量。 - 预处理范围：最终答案严格小于 2⁵⁰，所以最高位取到49（0-based），最多需要50个1，因此需要计算 i 从0到49、j 从0到50的所有组合数。
- 计算规则：采用动态规划递推。边界很简单：任何数选0个位置放1，只有1种方案（全0）；递推公式就是经典的
C(i,j) = C(i-1,j-1) + C(i-1,j)（选当前位为1 + 选当前位为0）。 - 作用：后面每一步判断“当前位填0时，剩余位数能产生多少种合法数”都可直接查表，效率极高。
二、核心逻辑：逐位构造答案（从高位到低位）
算法的核心思路其实很简单：从最高位（第49位）往最低位（第0位）遍历，逐位决定该二进制位是0还是1，最终拼出第n小的合法数。
我们以题目给出的例子推演：n=4，k=2，即需要找到二进制恰好有2个1的第4小的数。已知排序结果：3(11₂)、5(101₂)、6(110₂)、9(1001₂)。
初始状态
- 当前待确定位：最高位（第49位）
- 剩余需要填的1的个数：k=2
- 目标排名：n=4
- 答案初始值：0（二进制全0）
步骤1：遍历高位（第49位 ～ 第4位）
这些位非常高，计算一下：如果当前位填0，剩余位置能填出多少个“恰好2个1”的数？公式为 C(剩余位数, 剩余1个数)。剩余位数 = 当前位的下标，剩余1个数 = 2。计算发现，这些高位填0时，能生成的方案数远大于4。这意味着第4个数肯定不包含这些高位，所以所有高位全部填0。状态不变：k=2，n=4，ans=0。
步骤2：处理第3位（二进制 8 的位置，值为8）
- 计算：当前位填0时，剩余3个位置选2个1的方案数 =
C(3,2)=3； - 比较：目标排名 n=4 ＞ 方案数3；
- 判断：第4个数不在当前位填0的范围内，当前位必须填1；
- 更新状态：
- 排名减去填0的方案数：n=4-3=1（剩下只需找新排名第1的数）；
- 答案加上当前位的值：ans=0+8=8；
- 剩余需要填的1个数减1：k=2-1=1。
步骤3：处理第2位（二进制 4 的位置，值为4）
- 计算：当前位填0时，剩余2个位置选1个1的方案数 =
C(2,1)=2； - 比较：目标排名 n=1 ≤ 方案数2；
- 判断：第1个数在当前位填0的范围内，当前位填0；
- 状态不变：k=1，n=1，ans=8。
步骤4：处理第1位（二进制 2 的位置，值为2）
- 计算：当前位填0时，剩余1个位置选1个1的方案数 =
C(1,1)=1； - 比较：目标排名 n=1 ≤ 方案数1；
- 判断：第1个数在当前位填0的范围内，当前位填0；
- 状态不变：k=1，n=1，ans=8。
步骤5：处理第0位（二进制 1 的位置，值为1）
- 剩余需要填的1个数 k=1，必须填1才能满足条件；
- 更新答案：ans=8+1=9；
- 剩余1个数减1：k=0，结束遍历。
三、最终结果
最终构造出的数是 9，与题目示例输出完全一致。整个过程实际上就是利用组合数进行“进位制”式的决策，思路非常巧妙。
时间复杂度 & 额外空间复杂度
1. 总时间复杂度
分两部分：
- 初始化组合数：双重循环 mx×mx 次（mx=50），时间复杂度 O(mx²)；
- 核心构造逻辑：从高位到低位遍历50位，单次遍历仅做查表与判断，时间复杂度 O(mx)。
mx 是固定常数50，所以总时间复杂度为 O(1)——常数级时间，与输入规模无关。
2. 总额外空间复杂度
只开辟了一个固定大小的二维数组 comb[mx][mx+1] 存储组合数，mx=50 是固定常数，没有其他动态开辟的空间。因此额外空间复杂度同样是 O(1)。
总结
- 整体流程：预处理组合数 → 从高位到低位逐位确定二进制位（0/1） → 构造出答案；
- 核心判断：利用组合数计算当前位填0的方案数，与排名对比决定填0还是填1；
- 复杂度：时间和空间均为常数级 O(1)，效率极高，完全适配题目数据范围。
Go 完整代码如下：
package main
import "fmt"
const mx = 50
var comb [mx][mx + 1]int64
func init() {
// 预处理组合数
for i := range comb {
comb[i][0] = 1
for j := 1; j <= i; j++ {
comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
}
}
}
func nthSmallest(n int64, k int) (ans int64) {
for i := mx - 1; k > 0; i-- {
c := comb[i][k] // 第 i 位填 0 的方案数
if n > c {
// n 比较大，第 i 位必须填 1
n -= c
ans |= 1 << i
k-- // 维护剩余的 1 的个数
}
}
return
}
func main() {
n := int64(4)
k := 2
result := nthSmallest(n, k)
fmt.Println(result)
}
Python 完整代码如下：
# -*-coding:utf-8-*-
mx = 50
# 预处理组合数
comb = [[0] * (mx + 1) for _ in range(mx)]
for i in range(mx):
comb[i][0] = 1
for j in range(1, i + 1):
comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
def nth_smallest(n: int, k: int) -> int:
"""找到第 n 个恰好包含 k 个 1 的二进制数（从小到大）返回对应的整数值"""
ans = 0
i = mx - 1
while k > 0 and i >= 0:
c = comb[i][k] # 第 i 位填 0 的方案数
if n > c:
# n 比较大，第 i 位必须填 1
n -= c
ans |= 1 << i
k -= 1 # 维护剩余的 1 的个数
i -= 1
return ans
if __name__ == "__main__":
n = 4
k = 2
result = nth_smallest(n, k)
print(result)
C++ 完整代码如下：
#include
#include
const int mx = 50;
int64_t comb[mx][mx + 1];
void init_comb() {
for (int i = 0; i < mx; ++i) {
comb[i][0] = 1;
for (int j = 1; j <= i; ++j) {
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
}
}
int64_t nthSmallest(int64_t n, int k) {
int64_t ans = 0;
for (int i = mx - 1; k > 0; --i) {
int64_t c = comb[i][k]; // 在第 i 位填 0 的方案数
if (n > c) {
// n 比较大，第 i 位必须填 1
n -= c;
ans |= (1LL << i);
--k; // 剩余 1 的个数减 1
}
}
return ans;
}
int main() {
init_comb();
int64_t n = 4;
int k = 2;
int64_t result = nthSmallest(n, k);
std::cout << result << std::endl;
return 0;
}
