LeetCode 3821 题解：二进制中恰好 K 个 1 的第 N 小整数（C 语言实现）
核心思路
通过 组合数预处理 + 从高位向低位逐位决策 高效构造目标整数：
1. 预处理组合数表：计算 C[i][j]（i 位中选 j 个位置填 1 的方案数），范围 0 leq i,j leq 50。
2. 逐位决策：
- 从最高位（第 49 位）向最低位（第 0 位）遍历。
- 对当前位 p，计算 填 0 时剩余 p 位能构成的合法数数量 C(p, k)。
- 若 C(p, k) geq n：当前位填 0（目标数在填 0 的范围内）。
- 若 C(p, k) p 时：C[p][k] = 0，强制填 1（因填 0 无法满足 k 个 1 的条件）。
- k = 0 时：提前终止（后续位全 0）。
- 题目约束：1 leq k leq 50，1 leq n leq 10^{18}，答案 < 2^{50}，确保组合数计算安全。
复杂度分析
步骤 时间复杂度 说明
组合数预处理 O(1) 固定 51 times 51 次计算
逐位决策 O(1) 最多遍历 50 位
总时间复杂度 O(1) 与输入 n 无关
空间复杂度 O(1) 组合数表固定 51 times 51
测试用例验证
输入 (n, k) 输出 二进制 说明
(1, 1) 1 1 最小含 1 个 1 的整数
(1, 2) 3 11 最小含 2 个 1 的整数
(2, 2) 5 101 第 2 小的含 2 个 1 的整数
(3, 2) 6 110 第 3 小的含 2 个 1 的整数
(4, 2) 9 1001 第 4 小的含 2 个 1 的整数
此方法 100% 通过 LeetCode 3821 测试用例，且时间稳定在 O(1)。
