LeetCode 1356. 根據(jù)數(shù)字二進制下 1 的數(shù)目排序

????????給你一個整數(shù)數(shù)組?arr?。請你將數(shù)組中的元素按照其二進制表示中數(shù)字 1 的數(shù)目升序排序。如果存在多個數(shù)字二進制中?1?的數(shù)目相同，則必須將它們按照數(shù)值大小升序排列。

文章講解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 的個數(shù)
  1. 每次取末位，遇 1 則 ++count，有多少位就進行多少次；

     int bitCount(int n) {int count = 0; // 計數(shù)器while (n > 0) {if((n & 1) == 1)  ++count;  // 當前位是1，++countn >>= 1 ; // n向右移位}return count;
     }

  2. 每次消除最右的1，count 統(tǒng)計操作次數(shù)即可：

     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的數(shù)量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數(shù)量相同，比較數(shù)值大小return bitA < bitB; // 否則比較bit中1數(shù)量大小}
public:vector<int> sortByBits(vector<int>& arr) {sort(arr.begin(), arr.end(), cmp);return arr;}
};