【leetcode】1356. 根据数字二进制下 1 的数目排序（sort-integers-by-the-number-of-1-bits）（模拟）[简单]

链接

https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits/

耗时

解题：15 min
题解：6 min

题意

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

思路

结构体中记录整数值和整数二进制中 1 的数目，然后结构体排序。

时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)

AC代码

class Solution {
private:
    struct node {
        int val, cnt;
        bool operator < (const node &d) const {
            return cnt == d.cnt ? (val <= d.val) : (cnt < d.cnt);//从小到大
        }
    };
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<node> res;
        for(auto x : arr) {
            int x_backup = x;
            int cntx = 0;
            while(x) {
                if(x&1) cntx++;
                x >>= 1;
            }
            res.push_back((node){x_backup, cntx});
        }
        sort(res.begin(), res.end());
        vector<int> ans;
        for(auto x : res) {
            ans.push_back(x.val);
        }
        return ans;
    }
};