📘 題目敘述
給你兩個正整數 n 和 k。
請回傳「二進位表示中 恰好有 k 個 1」的正整數裡，第 n 小的那一個。
題目保證答案 嚴格小於 2^50。
條件限制
1 <= n <= 2501 <= k <= 50- 答案嚴格小於
2^50
🧠 解題思路（最後TLE）
我的想法是：我先用一個 bin（bool 陣列）表示「目前這個數的二進位哪些位元是 1」，並且從最小的開始（也就是最低位連續放 k 個 1：111...000）。
接著我要做的事情就是重複 n - 1 次：把目前的 bitmask 變成「下一個更大的、但 1 的數量仍然是 k」的 bitmask。
這其實是在做「固定 1 的個數的下一個組合（next combination）」。
所有變數
n,k：題目輸入，要找第n小、且有k個 1 的正整數bin：vector<bool>，bin[t] = true代表第t個 bit 是 1（我用t = 0當最低位）pos：目前最高的 1 出現到哪個 bit（用來最後把bin轉回數字時的最高位）ans：最後要回傳的整數count：掃描過程中，累計「目前遇到的 1 的數量」（用來把低位重新塞回去）i,j,l：迴圈索引用
🪜 主要流程步驟
1) 初始化成「最小的那個」
- 最小的數一定是：最低位開始連續放
k個 1，例如k = 3→0b111 - 所以我先做：
bin[0..k-1] = true- 其餘都是
false
2) 重複做 n - 1 次：產生下一個 bitmask（核心）
我在每一次迭代裡，從低位往高位掃描，找「可以往左移動的一顆 1」。
我在找的關鍵形狀
- 找到某個位置
j滿足： bin[j] == 1bin[j + 1] == 0
這代表這顆 1 可以「往更高位推一格」，讓整體數值變大，但仍保留 k 個 1。
做法分兩步
(A) 把這顆 1 往左推
bin[j] = 0bin[j + 1] = 1- 同時更新
pos = max(pos, j + 1)（因為最高位可能變大了）
(B) 把 j 左邊的低位重新整理成「最小」
- 我會用
count記錄我一路走來遇到多少個 1（包含要搬的那顆之前累積的） - 當找到可搬動位置後，我就把
0..j-1的 bit 重新排成： - 從最低位開始塞回
count顆 1，其餘補 0 - 這樣可以確保在「固定高位變大的前提下」，低位保持最小，才能得到「下一個最小的合法數」。
3) 把 bin 轉回整數
最後我從 pos（最高位）一路往 0 組回去：
- 每一位做：
ans = ans * 2 + (bin[l] ? 1 : 0)
💻 程式碼實作
class Solution {
public:
long long nthSmallest(long long n, int k) {
long long int ans = 0;
int pos = k - 1;
vector<bool> bin(51, false);
for (int i = 0; i < k; i++) {
bin[i] = true;
}
for (long long int i = 1; i < n; i++) {
int count = 0;
for (int j = 0; j < 50; j++) {
if (bin[j] && !bin[j + 1]) {
bin[j + 1] = true;
bin[j] = false;
pos = (pos > j + 1) ? pos : (j + 1);
for (int k = 0; k < j; k++) {
if (count > 0) {
bin[k] = true;
count--;
} else {
bin[k] = false;
}
}
break;
} else if (bin[j]) {
count++;
}
}
}
for (int l = pos; l >= 0; l--) {
ans = ans * 2 + (bin[l] ? 1 : 0);
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/contest/weekly-contest-486/problems/find-nth-smallest-integer-with-k-one-bits/