2026-05-29：二进制中恰好K个1的第N小整数。用go语言，给定两个正整数 n 和 k，要求你找到这样一个数：在它的二进制表示中，恰好有 k 个

福大大架构师每日一题

发布于 2026-05-29 13:13:37

120

2026-05-29：二进制中恰好K个1的第N小整数。用go语言，给定两个正整数 n 和 k，要求你找到这样一个数：在它的二进制表示中，恰好有 k 个比特位为 1。把所有满足条件的正整数按大小从小到大排序，返回其中第 n 个数。题目保证这个答案一定小于 2⁵⁰。

1 <= n <= 2⁵⁰。

1 <= k <= 50。

答案严格小于 2⁵⁰。

输入： n = 4, k = 2。

输出： 9。

解释：

二进制表示中恰好包含 k = 2 个 1 的前 4 个正整数分别是：

3 = 11₂。

5 = 101₂。

6 = 110₂。

9 = 1001₂。

题目来自力扣3821。

解题过程详解

一、前置准备：预处理组合数

这是算法的初始化步骤，在程序启动时自动执行，核心作用是提前计算好所有需要用到的组合数，为后续快速判断做准备。

1. 组合数的含义：C(i, j) 表示从 i 个位置中选 j 个位置放1 的总方案数，这正好对应「二进制数有j个1」的数量。
2. 预处理范围：因为答案严格小于 2⁵⁰，所以我们只需要计算到最高位50位的所有组合数（i 最大取49，j 最大取50）。
3. 计算规则：用动态规划递推
- • 边界：任何数选0个位置放1，都只有1种方案（全0）；
- • 递推：C(i,j) = C(i-1,j-1) + C(i-1,j)（选当前位为1 + 选当前位为0）。
4. 作用：后续每一步判断，都能直接查表得到方案数，不用重复计算。

二、核心逻辑：逐位构造答案（从高位到低位）

算法的核心思想：从最高位（第49位）到最低位（第0位），一位一位确定当前二进制位是0还是1，最终拼出第n小的数。

我们的目标：找二进制恰好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）

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 的位置，值为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 的位置，值为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. 剩余需要填的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 <iostream>
#include <cstdint>

constint 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;
    return0;
}