4 个与容器和库相关的题。

1356. Sort Integers by The Number of 1 Bits

Analysis

按照数字的二进制中 1 的个数进行排序，如果 1 的个数相等就按照自然数大小排序。
分析一下，完成这道题，其实需要解决 2 个问题：

算出每个数字中 1 的个数
排序

由于数字与其二进制中 1 的个数是对应的关系，所以使用 map 来保存这些数字比较方便（map 可以自动排序）。但是使用 map 会自动去除重复元素，这样结果就不对了。注意到这个题目的最大值是 $10^4$，这个数的二进制总共有 14 位，也就是说，这个题目的测试数据中不会存在 1 的个数超过 14 的数（实际上不可能有 14 位都是 1 的数，因为这个数超过了 $10^4$）。那就可以按照这些数据的二进制中 1 的个数分别存放，然后在排序，这样就可以解决重复的问题了。

Code

method 1

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        int size = arr.size(), maxcount = 0;
        vector<vector<int>> res(14, vector<int>());
        for(int i = 0; i < size; i++) {
            int tmp = __builtin_popcount(arr[i]);
            res[tmp].push_back(arr[i]);
            if(tmp > maxcount) maxcount = tmp;
        }
        vector<int> ret;
        for(int i = 0; i <= maxcount; i++) {
            sort(res[i].begin(), res[i].end());
            for(int j: res[i]) {
                ret.push_back(j);
            }
        }
        return ret;
    }
};

method 2

现在，再回到题目上，要求按照数字二进制中 1 的个数进行排序。对于面对对象的语言来讲，如果能把这个数字的二进制中 1 的个数作为这个类的一个成员变量，然后再用这个成员变量排序，不也可以得到结果吗？但遗憾的是，Leetcode 并不能自行构造类，所以只能“凑”一下了。

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        int size = arr.size();
        vector<int> bits(10001, 0);
        for(int i = 0; i < size; i++) {
            bits[arr[i]] = __builtin_popcount(arr[i]);
        }
        sort(arr.begin(), arr.end(), [&](int a, int b) {
            if(bits[a] != bits[b]) return bits[a] < bits[b];
            else return a < b;
        });
        return arr;
    }
};

实际上，求取 bits 数组的过程可以提前做好。

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        int size = arr.size();
        vector<int> bits(10001, 0);
        for(int i = 1; i <= 10000; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        sort(arr.begin(), arr.end(), [&](int a, int b) {
            if(bits[a] != bits[b]) return bits[a] < bits[b];
            else return a < b;
        });
        return arr;
    }
};