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 501 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)。
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 501 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)。
)
