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

1. Use STL sort() and __builtin_popcount():

  • __builtin_popcount(unsigned int) is a builtin function in gcc to show how many bits in a unsigned int
    • 2 -> 10 __builtin_popcount(2) = 1
    • 3 -> 11 __builtin_popcount(3) = 2
    • 7 -> 111 __builtin_popcount(7) = 3
    • 8 -> 1000 __builtin_popcount(8) = 1
  • the 3rd parameter of sort() can use a non-default sorting rule ```cpp //12 ms 10.3 MB

class Solution { public: vector sortByBits(vector& arr) { sort(arr.begin(), arr.end(), { int pa = builtin_popcount(a); int pb = builtin_popcount(b); return pa==pb ? a<b : pa<pb; });
return arr; } };

  2. <a name="u3mjG"></a>
  3. #### 2. Use STL sort():
  5. - the 3rd parameter function of sort() should be stated static or out of a class
  6. ```cpp
  7. //36 ms    10.1 MB
  9. class Solution {
  10. public:
  11.     vector<int> sortByBits(vector<int>& arr) {
  12.         sort(arr.begin(), arr.end(), [](int a, int b){
  13.             int pa = howManyBits(a);
  14.             int pb = howManyBits(b);
  15.             return pa==pb ? a<b : pa<pb;
  16.         });
  17.         return arr;
  18.     }
  20.     //return bits of a number
  21.     static int howManyBits(int num){
  22.         int count = 0;
  23.         while(num > 0){
  24.             if(num % 2 != 0){
  25.                 num = (num-1)/2;
  26.                 count++;
  27.             } else{
  28.                 num = num/2;
  29.             }
  30.         }        
  31.         return count;
  32.     }
  33. };

3. Use Merge Sort:

  1. //120 ms    26.6 MB
  3. class Solution {
  4. public:
  5.     vector<int> sortByBits(vector<int>& arr) {
  6.         vector<int> bit;
  8.         int n = arr.size();
  10.         //loop in arr
  11.         for(int i=0; i<n; i++){
  12.             //record number of bits
  13.             bit.push_back(howManyBits(arr[i]));
  14.         }
  16.         mergeSortAdv(arr, bit);
  18.         return arr;
  19.     }
  21. private:
  22.     //return bits of a number
  23.     int howManyBits(int num){
  24.         int count = 0;
  25.         while(num > 0){
  26.             if(num % 2 != 0){
  27.                 num = (num-1)/2;
  28.                 count++;
  29.             } else{
  30.                 num = num/2;
  31.             }
  32.         }
  34.         return count;
  35.     }
  37.     void mergeSortAdv(vector<int>& arr, vector<int>& bit){
  38.         mergeSortAdv(arr, bit, 0, arr.size()-1);
  39.     }
  41.     void mergeSortAdv(vector<int>& arr, vector<int>& bit, int l, int r){
  42.         if(l < r){
  43.             int m = l + (r-l) / 2;
  45.             mergeSortAdv(arr, bit, l, m);
  46.             mergeSortAdv(arr, bit, m+1, r);
  48.             merge(arr, bit, l, m, r);
  49.         }
  50.     }
  52.     void merge(vector<int>& arr, vector<int>& bit, int l, int m, int r){
  54.         vector<int> L_arr, R_arr;
  55.         vector<int> L_bit, R_bit;
  57.         int n1 = m - l + 1;
  58.         int n2 = r - m;
  59.         int i, j, k;
  61.         for(i = 0; i < n1; i++){
  62.             L_arr.push_back(arr[l + i]);
  63.             L_bit.push_back(bit[l + i]);
  64.         }
  65.         for(j = 0; j < n2; j++){
  66.             R_arr.push_back(arr[m + 1 + j]);
  67.             R_bit.push_back(bit[m + 1 + j]);
  68.         }
  70.         i = 0;
  71.         j = 0;
  72.         k = l;
  74.         while(i < n1 && j < n2){
  75.             if(L_bit[i] <= R_bit[j]){
  76.                 if(L_bit[i] < R_bit[j]){
  77.                     bit[k] = L_bit[i];
  78.                     arr[k] = L_arr[i];
  79.                     i++;
  80.                 } 
  81.                 else if(L_bit[i] == R_bit[j]){
  82.                     if(L_arr[i] <= R_arr[j]){
  83.                         bit[k] = L_bit[i];
  84.                         arr[k] = L_arr[i];
  85.                         i++;
  86.                     } else {
  87.                         bit[k] = R_bit[j];
  88.                         arr[k] = R_arr[j];
  89.                         j++;
  90.                     }
  91.                 }
  93.             } else {
  94.                 bit[k] = R_bit[j];
  95.                 arr[k] = R_arr[j];
  96.                 j++;
  97.             }
  98.             k++;
  99.         }
  101.         while(i < n1){
  102.             bit[k] = L_bit[i];
  103.             arr[k] = L_arr[i];
  104.             i++;
  105.             k++;
  106.         }
  108.         while(j < n2){
  109.             bit[k] = R_bit[j];
  110.             arr[k] = R_arr[j];
  111.             j++;
  112.             k++;
  113.         }
  114.     }
  115. };

4. Use Swap Sort:

//72 ms    10.4 MB

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<int> bits;

        int n = arr.size();

        //loop in arr
        for(int i=0; i<n; i++){
            //record number of bits
            bits.push_back(howManyBits(arr[i]));
        }

        swapSortAdv(arr, bits);

        return arr;
    }

private:
    //return bits of a number
    int howManyBits(int num){
        int count = 0;
        while(num > 0){
            if(num % 2 != 0){
                num = (num-1)/2;
                count++;
            } else{
                num = num/2;
            }
        }

        return count;
    }

    //swap bits and corresponding arr positions
    void swapSortAdv(vector<int>& arr, vector<int>& bits){
        int n = arr.size();
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                if(bits[i] > bits[j]){
                    swap(bits[i], bits[j]);
                    swap(arr[i], arr[j]);
                }
                if((arr[i] > arr[j]) && (bits[i] == bits[j])){
                    swap(arr[i], arr[j]);
                }
            }
        }
    }
};