1356. Sort Integers by The Number of 1 Bits (easy)

Q:

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the sorted array.

Example 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]

Example 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.

Example 3:

Input: arr = [10000,10000]
Output: [10000,10000]

Example 4:

Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]

Example 5:

Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]

Constraints:

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10^4

A:
依然是根据一个部分，来排序的问题。 经典的priority_queue

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        struct A
        {
            int val, count1;
            A(int v, int c):val(v),count1(c){}
        };
        struct compareA
        {
            bool operator()(A const& a1, A const& a2)
            {
                if(a1.count1 == a2.count1)
                {
                    return a1.val > a2.val;
                }
                return a1.count1 > a2.count1;
            }
        };
        priority_queue<A, vector<A>, compareA> Q;
        for(auto v : arr)
        {
            Q.push(  A(v, count1(v))   );
        }
        vector<int> res;
        while(! Q.empty())
        {
            A a = Q.top();
            Q.pop();
            res.push_back(a.val);
        }
        return res;
    }
private:
    int count1(int val) // val >=0
    { 
        int res = 0;
        while(val!=0)
        {
            if(val & 1 == 1)
            {
                res++;
            }            
            val = val>>1;
        }
        return res;
    }
};

错误：

vector<int> res;  一开始想加上 default size, 就写成了
vector<int> res(arr.size);  这样是对的。等发现不需要写的时候，就删掉了参数，可是忘记删掉括号了