【原】根据二进制下1的数目排序--LeetCode

KookNut39 2021-12-15

展开全文

上周广联达笔试的时候，有一道题是我之前在LeetCode上见过的题，但是我在考试过程中只记得大体思路，是调用了一个C++的库函数，可以直接计算1的数量，具体调用哪个库函数记不清楚了。于是下来又搜索了一下这道题，然后回顾了一下实现思路，顺便学习一下其他方法。

题目描述：
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits

题解1：C++系统库函数
使用这个__builtin_popcount函数可以直接传一个整形数据，然后计算出1的个数。
题解2：手动计算数据中含1的个数，进行排序

//全局变量储存数据
int Bit[0x10000] = { 0 };
int Get_1_From_Int(int x)
{
int Sum = 0;
while (x)
{
//统计一个数字中1的数量
Sum += x & 1;
//每次向右移一位
x >>= 1;
}
//总共1的个数
return Sum;
}
vector<int> SortByBits(vector<int>& Arr) 
{
    //C+11新特性，新for循环
for (auto x : Arr)
{
Bit[x] = Get_1_From_Int(x);
}
//使用Lambda函数内嵌，相当于函数指针的作用
sort(Arr.begin(), Arr.end(), [&](int x, int y)
{
return Bit[x] == Bit[y] ? x < y : Bit[x] < Bit[y];
});
return Arr;
}
void main()
{
setlocale(LC_ALL, "chs");//识别中文
vector<int> v1;
v1.push_back(5);
v1.push_back(6);
v1.push_back(7);
v1.push_back(8);
v1.push_back(9);
v1.push_back(1);
v1.push_back(2);
vector<int> v5;
v5 = SortByBits(v1);
getchar();
/*
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
*/
getchar();
}