求二进制含n个1的第k个数的常数时间算法

核心解法 #

二进制中恰好包含n个1的数按升序排列，本质等价于从非负整数的二进制位位置中选n个位置的组合，按数值从小到大排序（数值大小对应组合的二进制位取值）。我们可以利用组合数的性质，通过逐位确定1的位置来高效求解，避免暴力生成所有可能的数。

算法步骤 #

1. 组合数的安全计算

首先需要实现一个能计算组合数C(a, b)的函数，注意处理溢出问题：当计算过程中结果超过当前剩余的k值时，直接返回一个大于k的数即可（无需精确计算），避免溢出。示例伪代码：

function comb(m, t, max_k):
    if m < t or t < 0:
        return 0
    if t == 0 or m == t:
        return 1
    t = min(t, m - t)  # 利用对称性减少计算量
    res = 1
    for i from 1 to t:
        if res > max_k // (m - t + i):
            return max_k + 1  # 溢出，直接返回大于max_k的值
        res = res * (m - t + i) // i
        if res > max_k:
            return res
    return res

2. 逐位确定1的位置

通过组合数判断每一位是否为1，步骤如下：

• 初始化：result = 0，remaining_ones = n，current_k = k
• 循环直到remaining_ones == 0：
  1. 二分查找当前位：找到最小的m，使得comb(m, remaining_ones, current_k) < current_k <= comb(m+1, remaining_ones, current_k)
  2. 标记当前位为1：将m位设置到结果中：result |= (1 << m)
  3. 更新状态：current_k -= comb(m, remaining_ones, current_k)，remaining_ones -= 1

示例验证（n=2，k=3） #

1. 初始状态：remaining_ones=2，current_k=3
2. 第一次查找：找m使得comb(m,2,3) <3 <=comb(m+1,2,3)
   • comb(2,2,3)=1 <3，comb(3,2,3)=3 >=3 → m=2
   • 结果更新为1<<2=4，current_k=3-1=2，remaining_ones=1
3. 第二次查找：找m使得comb(m,1,2) <2 <=comb(m+1,1,2)
   • comb(1,1,2)=1 <2，comb(2,1,2)=2 >=2 → m=1
   • 结果更新为4 | (1<<1)=6，remaining_ones=0，循环结束
4. 最终结果为6，与示例一致。

复杂度分析 #

• 时间复杂度：每一步通过二分查找定位位位置，时间为O(log k)，共n步，总复杂度为O(n log k)。当n固定时，这几乎是常数时间（log k增长极慢）。
• 空间复杂度：O(1)，无需额外存储所有组合。

对比暴力法 #

暴力法需要生成所有含n个1的数直到第k个，时间复杂度为O(k)，当k很大（如1e9）时完全不可行。而本算法仅通过组合数判断和二分查找，就能快速定位结果，效率提升显著。

内容的提问来源于stack exchange，提问作者Lewis Trem