按 1 位数对整数排序。我使用一种排序函数对向量进行排序？但为什么排序不起作用？

Question

按 1 的位数对整数排序

示例测试用例：

示例 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]

注意： 在上面的测试用例示例中，测试用例的每个元素只有一个设置位（1）

Answer 1

vector<int>vec 是地图中副本的副本，然后被丢弃。尝试：

for(auto& entry:mp){
    vector<int>&vec=entry.second;
    sort(vec.begin(),vec.end());
}

您的其他 for 循环也应使用引用以提高效率，但不会影响行为。

Answer 2

作为您在 //This sort function ... 中的迭代引用 mp 作为映射内部值的副本，排序函数不会对其中的向量进行排序，而是对它的副本进行排序。这不影响原来的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;
    }
};

虽然您的解决方案中存在更多设计问题，但这将是一个修改最少的解决方案。

Answer 3

这是内存高效且快速的解决方案。我不知道你为什么要使用地图和额外的矢量。我们可以在没有任何额外内存的情况下有效地解决这个问题。我们只需要创建一个 Comparator 函数，它将根据我们自己的要求对元素进行排序。如果您需要进一步的代码帮助（或者如果您觉得难以理解我的代码），请在评论中告诉我。我正在使用 __builtin_popcount() 函数，它将 return 设置数字中的位数。

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;
}
};

Answer 4

我假设 OP 只是在学习，因此摆弄各种数据结构等可以具有一定的教育价值。尽管如此，只有一条评论指出问题的开始方法是错误的，练习的重点是找到一种比较数字的自定义方法，首先按位数，然后按值。

提供 std::sort 是允许的（OP 使用它），我想整个解决方案在概念上归结为 sth likes this（但我没有用 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>{});
    }
};

可能还可以进一步改进，但我会把它作为分析的起点。

Answer 5

该问题已经过评估，并且已经解释了修复方法。

我想给出2个additional/alternative个解决方案。

在 C++17 中，我们有 std::bitset 计数函数。请参阅 here
而在 C++20 中我们直接有 std::popcount 函数。请参阅 here。

（像我这样的老人和头发花白的人还会在《Hackers Delight》一书中找到另外 5 个最有效的解决方案）

两种变体都导致使用 std::sort 和 lambda 的单语句解决方案。

请看：

#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';
    }
}

按 1 位数对整数排序。我使用一种排序函数对向量进行排序？但为什么排序不起作用？

Sort Integers by The Number of 1 Bits . I used one sort function to sort the vector ? But why sort is not working?

c++

sorting

bit-manipulation

counting