位运算 | 1356. 根据数字二进制下 1 的数目排序

LeetCode 1356. 根据数字二进制下 1 的数目排序

        给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

文章讲解https://www.programmercarl.com/1356.%E6%A0%B9%E6%8D%AE%E6%95%B0%E5%AD%97%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%B8%8B1%E7%9A%84%E6%95%B0%E7%9B%AE%E6%8E%92%E5%BA%8F.html#c-%E4%BB%A3%E7%A0%81

• 思路：计算二进制表示中 1 的个数
  1. 每次取末位，遇 1 则 ++count，有多少位就进行多少次；

     int bitCount(int n) {int count = 0; // 计数器while (n > 0) {if((n & 1) == 1)  ++count;  // 当前位是1，++countn >>= 1 ; // n向右移位}return count;
     }

  2. 每次消除最右的1，count 统计操作次数即可：

     int bitCount(int n) {int count = 0;while (n) {n &= (n - 1); // 清除最低位的1++count;}return count;
     }

     

• 代码：

class Solution {
private:static int bitCount(int n) { // 计算n的二进制中1的数量int count = 0;while(n) {n &= (n -1); // 清除最低位的1count++;}return count;}static bool cmp(int a, int b) {int bitA = bitCount(a);int bitB = bitCount(b);if (bitA == bitB) return a < b; // 如果bit中1数量相同，比较数值大小return bitA < bitB; // 否则比较bit中1数量大小}
public:vector<int> sortByBits(vector<int>& arr) {sort(arr.begin(), arr.end(), cmp);return arr;}
};