📘 題目敘述
給你一個整數陣列 arr。
請你依照每個整數的二進位表示中 1 的個數，將陣列中的整數由小到大排序。
如果兩個整數的 1 的個數相同，就依照整數本身的大小由小到大排序。
請回傳排序後的陣列。
條件限制
1 <= arr.length <= 5000 <= arr[i] <= 10^4
🧠 解題思路
我先把每個數字 i 轉成一個排序用的 key：
- key 的第一部分：
i的二進位裡有幾個1（記成count） - key 的第二部分：數字本身
i
所以我用一個 vector<pair<int,int>> s 存 (count, i)。
接著直接對 s 排序，因為 pair 的排序規則就是：
- 先比第一個元素（count）
- count 相同再比第二個元素（i）
剛好完全符合題目需求。
計算 count 我用的是經典技巧：
n = n & (n - 1)
每做一次就會刪掉 n 最右邊的一個 1，所以做幾次就代表有幾個 1。
排序完後我再把 pair 裡的第二個值 i 依序拿出來放進 ans。
所有變數
s：存(count, i)的陣列，用來排序count：某個數字二進位中1的個數n：用來計算 bit count 的暫存值（會被反覆做n & (n-1)直到變 0）ans：排序後的答案陣列
🪜 主要流程步驟
1. 把每個數字轉成 (1 的個數, 原數字) 的 pair
我掃過 arr 的每個 i：
- 用
n = i當作暫存 - 用 while 迴圈把
n的每個 1 刪掉一次 - 刪一次
count++ - 最後得到
(count, i)，push 進s
2. 對 s 排序
我做 sort(s.begin(), s.end())。
因為 pair 的排序規則剛好就是先比 count，再比 i，所以不用自己寫比較器。
3. 把排序後的結果取回成答案
排序後的 s 已經是正確順序，我把每個 pair 的第二個元素 b 依序 push 進 ans。
4. 回傳 ans
回傳最後的排序結果。
⏱️ 複雜度
- 時間複雜度：
O(n log n + n * bits)n是arr長度。排序是n log n，每個數字計算 bit count 最多做約 14 次（因為arr[i] <= 10^4）。 - 空間複雜度：
O(n)s和ans都是長度n。
💻 程式碼實作
class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
vector<pair<int, int>> s;
for (int i : arr) {
int count = 0;
int n = i;
while (n > 0) {
n = n & (n - 1); // 刪掉最右側的1
count++;
}
s.push_back({count, i});
}
sort(s.begin(), s.end());
vector<int> ans;
for (auto& [a, b] : s) {
ans.push_back(b);
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/