2026-05-29 二进制中恰好K个1的第N小整数 Go语言

解题过程详解

先说一个核心判断：这道题本质上是“按二进制字典序构造第N个满足条件的数”，而关键就在于组合数的灵活运用。我们一步一步来拆解。

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

在正式动手之前，先把组合数表提前算好——这相当于是算法的“弹药库”，后续每个决策都能直接查表，不用临时算。

• 组合数的含义：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）

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 
#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;
}