按每个整数中 1 位的数量对数组中的整数进行排序

Question

给定一个整数数组arr。您必须按二进制表示中 1 的数量对数组中的整数进行升序排序，如果两个或多个整数具有相同数量的 1，则必须按升序对它们进行排序。

Return 排序后的数组。

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]

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.

所以，我在这里使用了 Brian Kernigham 的算法来计算数组中每个整数中 1 的位数。这是我到目前为止编写的代码：-

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        //firstly sort the input array
        sort(arr.begin(), arr.end());
        
        
        vector<int> count;
        //Using Brian Kernigham's Algorithm
        for(int i =0; i<arr.size(); i++){
            while(arr[i]){
                arr[i] = arr[i] & (arr[i] -1);
                count[i] ++;
            }
        } 
    }
};

但是，我不知道如何组合 count[] 数组和输入数组 arr[] 以获得输出。我想过使用map() C++的STL，但是由于函数需要return vector<int>，所以我放弃了它的想法。

有人可以提供进一步的解决方案吗？另外，请不要共享任何使用预定义函数 builtin_popcount()

的代码

Answer 1

最简单（但不是最有效）的方法是将数字和计数一起存储在一个容器中，对其进行排序，然后提取数字：

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<std::pair<int,int> temp;
        
        for(int i =0; i<arr.size(); i++){
            int count = 0;
            while(arr[i]){
                arr[i] = arr[i] & (arr[i] -1);
                count++;
            }
            temp.emplace_back(count,arr[i]);
        } 
       
        std::sort(temp.begin(),temp.end());   

        // extract the numbers again:
        std::vector<int> numbers;
        // ...
        return numbers;
    }
};

std::sort不稳定，所以如果先对数字进行排序，然后再对设置的位数进行排序，则必须使用std::stable_sort。另一方面，std::pair<int,int> 确实有一个 operator< 可以与 std::sort 一起使用，根据 first 排序，然后 second.

或者，您可以编写一个比较器来对数字进行排序。这不会像上面那样有所有不必要的复制，但它会调用函数来计算多余的位数：

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
       std::sort(arr.begin(), arr.end(), [](int a,int b) {
               // count bits here
               auto n_bits_a = count_bits(a);
               auto n_bits_b = count_bits(b);
               if (n_bits_a == n_bits_b) return a < b;
               return n_bits_a < n_bits_b; });
        return arr;
    }
};

如果我们再次使用 std::pair<int,int> 已经具有所需顺序的事实，比较器可以写得更紧凑：

std::sort(arr.begin(), arr.end(), [](int a,int b) {
    auto proj = [](int x) { return std::pair<int,int>{ count_bits(x),x}; };
    return proj(a) < proj(b);
});

尚不完全清楚，为什么函数通过引用和 returns 向量来获取向量。上面也是对参数进行排序。

Answer 2

这是一个使用 std::bitset 的解决方案，它可以更轻松地处理位。 std::bitset 有一个 count() 函数，将 returns 位数设置为 1，您可以在您提供的比较器函数中使用它 std::sort():

#include <bitset>
#include <algorithm>
#include <vector>

class Solution {
public:
    std::vector<int> sortByBits(std::vector<int>& arr) {
        std::vector<int> vec = arr;

        std::sort(vec.begin(), vec.end(),
            [](int a, int b) { 
                std::bitset<32> ba(a);
                std::bitset<32> bb(b);
                if (ba.count() == bb.count())
                    return a < b;
                else
                    return ba.count() < bb.count();
            });

        return vec;
    }
    
};

这里是 Demo。

按每个整数中 1 位的数量对数组中的整数进行排序

Sort Integers in an array by the number of 1 Bits in each integer

c++

arrays

bit-manipulation

bit