解题思路与逐位构造详解

核心判断：本题实质是按二进制字典序筛选第N个含定数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时，剩余位数能生成多少合法数”直接查表，时间复杂度 O(1)。

二、逐位构造：从高位向低位决策

算法核心：从最高位（第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）

1. 计算：当前位填0时，剩余3个位置选2个1的方案数 = C(3,2)=3；
2. 比较：目标排名 n=4 ＞ 方案数3；
3. 决策：第4个数不在当前位填0的范围内，故当前位必须填1；
4. 更新状态：
   • 排名减去填0方案数：n=4-3=1（后续找新排名第1的数）；
   • 答案加上当前位值：ans=0+8=8；
   • 剩余需填1个数减1：k=2-1=1。

步骤3：处理第2位（二进制值4）

1. 计算：当前位填0时，剩余2个位置选1个1的方案数 = C(2,1)=2；
2. 比较：目标排名 n=1 ≤ 方案数2；
3. 决策：第1个数在当前位填0范围内，故当前位填0；
4. 状态不变：k=1，n=1，ans=8。

步骤4：处理第1位（二进制值2）

1. 计算：当前位填0时，剩余1个位置选1个1的方案数 = C(1,1)=1；
2. 比较：目标排名 n=1 ≤ 方案数1；
3. 决策：第1个数在当前位填0范围内，故当前位填0；
4. 状态不变：k=1，n=1，ans=8。

步骤5：处理第0位（二进制值1）

1. 剩余需填1个数 k=1，必须填1才能满足条件；
2. 更新答案：ans=8+1=9；
3. 剩余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)。

总结

1. 整体流程：预处理组合数 → 从高位到低位逐位确定二进制位（0/1） → 构造答案；
2. 核心判断：利用组合数计算当前位填0的方案数，对比排名决定填0或1；
3. 复杂度：时间与空间均为常数级 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;
}

来源：互联网