Hard

题目描述

给定两个正整数 n 和 k。

返回第 n 个具有恰好 k 个1的二进制表示的最小正整数。保证答案严格小于 2^50。

示例 1：

输入: n = 4, k = 2
输出: 9
解释:
具有恰好 k = 2 个1的二进制表示的4个最小正整数是:
    3 = 11₂
    5 = 101₂
    6 = 110₂
    9 = 1001₂

示例 2：

输入: n = 3, k = 1
输出: 4
解释:
具有恰好 k = 1 个1的二进制表示的3个最小正整数是:
    1 = 1₂
    2 = 10₂
    4 = 100₂

约束：

  • 1 <= n <= 2^50
  • 1 <= k <= 50
  • 答案严格小于 2^50

提示：

  • 由于答案严格小于 2^50，我们可以遍历结果的位数（长度）。
  • 预计算二项式系数 C(n, k) 来统计给定长度下恰好有 k 个设置位的数字数量。
  • 首先确定最高有效位的位置，然后基于剩余计数 n 从 MSB 到 LSB 贪心地确定剩余位。

解题思路

这是一个组合数学和位操作的问题。核心思路是利用二项式系数来计算具有特定位数和设置位数的数字个数。

算法思路：

  1. 预计算组合数：预计算 C(i,j) 表示从 i 个位置中选择 j 个位置放置1的方案数，这直接对应了有 i 位且恰好有 j 个1的数字个数。

  2. 确定结果的位数：从小到大枚举可能的位数 bits，对于每个位数，计算有多少个数字恰好有 k 个1。如果累计数量不够 n，则继续增加位数。

  3. 贪心构造：一旦确定了位数，就从最高位开始贪心构造。对于每一位：

    • 如果该位设为0，计算剩余位数中放置剩余1的方案数
    • 如果这个方案数大于等于剩余需要的数量 n，则该位设为0
    • 否则该位必须设为1，并从 n 中减去不选择该位的方案数

  4. 时间优化：由于答案小于 2^50，最多需要考虑50位，组合数的计算也是有界的。

这种方法本质上是在所有满足条件的数字构成的有序序列中，通过组合数学快速定位第n个数字，避免了暴力枚举。

代码实现

class Solution {
public:
    long long nthSmallest(long long n, int k) {
        // 预计算组合数 C(i, j)
        vector<vector<long long>> C(51, vector<long long>(51, 0));
        for (int i = 0; i <= 50; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = C[i-1][j-1] + C[i-1][j];
                if (C[i][j] > 1e18) C[i][j] = 1e18; // 防止溢出
            }
        }
        
        // 找到结果的位数
        int bits = k;
        long long total = 0;
        while (total < n) {
            total += C[bits-1][k-1];
            if (total < n) bits++;
        }
        
        // 贪心构造结果
        long long result = 0;
        n -= (total - C[bits-1][k-1]); // 调整n为在当前位数下的相对位置
        
        for (int pos = bits - 1; pos >= 0 && k > 0; pos--) {
            if (k == 1) {
                // 只剩一个1，放在最低位
                result |= (1LL << (k-1));
                break;
            }
            
            long long count = (pos >= k-1) ? C[pos][k-1] : 0;
            if (count < n) {
                // 当前位必须是1
                result |= (1LL << pos);
                n -= count;
                k--;
            }
        }
        
        return result;
    }
};

class Solution:
    def nthSmallest(self, n: int, k: int) -> int:
        # 预计算组合数 C(i, j)
        C = [[0] * 51 for _ in range(51)]
        for i in range(51):
            C[i][0] = 1
            for j in range(1, i + 1):
                C[i][j] = C[i-1][j-1] + C[i-1][j]
                if C[i][j] > 10**18:
                    C[i][j] = 10**18  # 防止溢出
        
        # 找到结果的位数
        bits = k
        total = 0
        while total < n:
            total += C[bits-1][k-1]
            if total < n:
                bits += 1
        
        # 贪心构造结果
        result = 0
        n -= (total - C[bits-1][k-1])  # 调整n为在当前位数下的相对位置
        
        pos = bits - 1
        while pos >= 0 and k > 0:
            if k == 1:
                # 只剩一个1，放在最低位
                result |= (1 << (k-1))
                break
            
            count = C[pos][k-1] if pos >= k-1 else 0
            if count < n:
                # 当前位必须是1
                result |= (1 << pos)
                n -= count
                k -= 1
            pos -= 1
        
        return result

public class Solution {
    public long NthSmallest(long n, int k) {
        // 预计算组合数 C(i, j)
        long[,] C = new long[51, 51];
        for (int i = 0; i <= 50; i++) {
            C[i, 0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i, j] = C[i-1, j-1] + C[i-1, j];
                if (C[i, j] > 1000000000000000000L) C[i, j] = 1000000000000000000L; // 防止溢出
            }
        }
        
        // 找到结果的位数
        int bits = k;
        long total = 0;
        while (total < n) {
            total += C[bits-1, k-1];
            if (total < n) bits++;
        }
        
        // 贪心构造结果
        long result = 0;
        n -= (total - C[bits-1, k-1]); // 调整n为在当前位数下的相对位置
        
        for (int pos = bits - 1; pos >= 0 && k > 0; pos--) {
            if (k == 1) {
                // 只剩一个1，放在最低位
                result |= (1L << (k-1));
                break;
            }
            
            long count = (pos >= k-1) ? C[pos, k-1] : 0;
            if (count < n) {
                // 当前位必须是1
                result |= (1L << pos);
                n -= count;
                k--;
            }
        }
        
        return result;
    }
}

var nthSmallest = function(n, k) {
    let count = 0;
    let num = 0;
    
    while (count < n) {
        num++;
        if (countOnes(num) === k) {
            count++;
        }
    }
    
    return num;
};

function countOnes(num) {
    let count = 0;
    while (num > 0) {
        count += num & 1;
        num >>= 1;
    }
    return count;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(50²)
空间复杂度O(50²)

说明：

  • 时间复杂度：预计算组合数需要O(50²)，确定位数最多需要O(50)次，构造结果需要O(50)次，总体为O(50²)
  • 空间复杂度：主要是存储组合数的二维数组，需要O(50²)的空间