按 1 位的數量對整數進行排序
Leetcode： 問題鏈接
示例測驗用例：
示例 1：
Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]\
示例 2：
Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.
我的解決方案：
class Solution {
public:
unsigned int setBit(unsigned int n){
unsigned int count = 0;
while(n){
count = n & 1;
n >>= 1;
}
return count;
}
vector<int> sortByBits(vector<int>& arr) {
map<int,vector<int>>mp;
for(auto it:arr){
mp[setBit(it)].push_back(it);
}
for(auto it:mp){
vector<int>vec;
vec=it.second;
sort(vec.begin(),vec.end()); //This Sort Function of vector is not working
}
vector<int>ans;
for(auto it:mp){
for(auto ele:it.second){
ans.push_back(ele);
}
}
return ans;
}
};
在我的代碼中，為什么排序功能不起作用？
[1024,512,256,128,64,32,16,8,4,2,1]
對于上面的測驗用例輸出是[1024,512,256,128,64,32,16,8,4,2,1]因為排序功能不起作用。正確的輸出是[1,2,4,8,16,32,64,128,256,512,1024]
注意： 在上面的示例測驗用例中，測驗用例的每個元素只有一個 set-bit(1)
uj5u.com熱心網友回復：
由于您的迭代是//This sort function ...
指mp映射中值的副本，因此 sort 函式不會對其中的向量進行排序，而是對它的副本進行排序。vector<int>里面不影響原來的mp。因此，不會產生影響。您應該將地圖內的矢量作為參考，如下所示：
class Solution {
public:
unsigned int setBit(unsigned int n) {
unsigned int count = 0;
while (n) {
count = n & 1;
n >>= 1;
}
return count;
}
vector<int> sortByBits(vector<int>& arr) {
map<int, vector<int>>mp;
for (auto it : arr) {
mp[setBit(it)].push_back(it);
}
for (auto& it : mp) {
sort(it.second.begin(), it.second.end()); //Now the sort function works
}
vector<int>ans;
for (auto it : mp) {
for (auto ele : it.second) {
ans.push_back(ele);
}
}
return ans;
}
};
盡管您的解決方案中有更多設計問題，但這將是一個修改最少的解決方案。
uj5u.com熱心網友回復：
vector<int>vec是地圖中的副本的副本，然后被丟棄。嘗試：
for(auto& entry:mp){
vector<int>&vec=entry.second;
sort(vec.begin(),vec.end());
}
您的其他 for 回圈也應該使用參考來提高效率，但它不會影響行為。
uj5u.com熱心網友回復：
我假設 OP 只是在學習，所以擺弄各種資料結構等可以帶來一些教育價值。盡管如此，只有一條評論指出問題的起始方法是錯誤的，練習的重點是找到一種自定義方法來比較數字，首先按位數，然后按值。
如果std::sort允許（OP 使用它），我想整個解決方案在概念上歸結為喜歡這個（但我還沒有針對 LeetCode 驗證它）：
template <typename T>
struct Comp
{
std::size_t countBits(T number) const
{
size_t count;
while(number) {
count = number & 1;
number>>=1;
}
return count;
}
bool operator()(T lhs, T rhs) const
{
/*
auto lb{countBits(lhs)};
auto rb{countBits(rhs)};
return lb==rb ? lhs < rhs : lb < rb;
* The code above is the manual implementation of the line below
* that utilizes the standard library
*/
return std::tuple{countBits(lhs), lhs} < std::tuple{countBits(rhs), rhs};
}
};
class Solution {
public:
void sortByBits(vector<int>& arr) {
std::sort(begin(arr), end(arr), Comp<int>{});
}
};
可能它可以進一步改進，但我會把它作為分析的起點。
uj5u.com熱心網友回復：
這是記憶體高效且快速的解決方案。我不知道你為什么要使用地圖和額外的矢量。我們可以在沒有任何額外記憶體的情況下有效地解決這個問題。我們只需要創建一個 Comparator 函式，它會根據我們自己的要求對元素進行排序。如果您需要進一步的代碼幫助（或者如果您發現難以理解我的代碼），請在評論中告訴我。我正在使用 __builtin_popcount() 函式，它將回傳一個數字中設定的位數。
bool sortBits(const int a, const int b){ //Comparator function to sort elements according to number of set bits
int numOfBits1 = __builtin_popcount(a);
int numOfBits2 = __builtin_popcount(b);
if(numOfBits1 == numOfBits2){ //if number of set bits are same, then sorting the elements according to magnitude of element (greater/smaller element)
return a < b;
}
return (numOfBits1 < numOfBits2); //if number of set bits are not same, then sorting the elements according to number of set bits in element
}
class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
sort(arr.begin(),arr.end(), sortBits);
return arr;
}
};
uj5u.com熱心網友回復：
該問題已被評估，并且已對修復進行了詳細解釋。
我想提供 2 個附加/替代解決方案建議。
- 在 C 17 中，我們有
std::bitsetcount 函式。請看這里 - 而在 C 20 中，我們直接擁有該
std::popcount函式。請看這里。
（像我這樣的老年人和白發的人也會在“Hackers Delight”一書中找到另外 5 個最有效的解決方案）
兩種變體都導致使用std::sortlambda 的單陳述句解決方案。
請參見：
#include <algorithm>
#include <vector>
#include <iostream>
#include <bitset>
// Solution
class Solution {
public:
std::vector<int> sortByBits(std::vector<int>& arr) {
std::sort(arr.begin(), arr.end(), [](const unsigned int i1, const unsigned int i2)
{ size_t c1{ std::bitset<14>(i1).count() }, c2{ std::bitset<14>(i2).count() }; return c1 == c2 ? i1 < i2 : c1 < c2; });
//{ int c1=std::popcount(i1), c2=std::popcount(i2); return c1 == c2 ? i1 < i2 : c1 < c2; });
return arr;
}
};
// Test
int main() {
std::vector<std::vector<int>> testData{
{0,1,2,3,4,5,6,7,8},
{1024,512,256,128,64,32,16,8,4,2,1}
};
Solution s;
for (std::vector<int>& test : testData) {
for (const int i : s.sortByBits(test)) std::cout << i << ' ';
std::cout << '\n';
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/426651.html