[LeetCode] 1356. Sort Integers by The Number of 1 Bits 根據數字二進制下1 的數目排序

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the array after sorting it.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Constraints:

1 <= arr.length <= 500
0 <= arr[i] <= 104

這道題給了一個數組 arr，讓我們給數組中的數字排序，按照數字的二進制表示中的1的個數從少到多排序，如果1的個數相同，則按照數字從小到大排。其實主要就是考察了一個求數字的二進制表示中的1的個數，計算方法是用個 while 循環，每次通過'與'上1來得到最低位上的數字，如果得到1，則計數器自增1，然后將數字向右平移一位。知道了如何統計1的個數，這道題就沒啥難度了，這里博主最開始的做法是將統計的個數和原數字本身組成一個數對兒，放入到一個新的數組中，然后對這個新數字進行自定義排序，排序的方法是首先按1的個數從小到大排，若個數相等，則按原數字從小到大排。最后只需要按順序從排序后的數組中提取原數字加入到結果 res 中即可，參見代碼如下：

解法一：

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<int> res;
        vector<vector<int>> nums;
        for (int num : arr) {
            int cnt = 0, d = num;
            while (d > 0) {
                cnt += d & 1;
                d >>= 1;
            }
            nums.push_back({cnt, num});
        }
        sort(nums.begin(), nums.end(), [](vector<int> &a, vector<int> &b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
        });
        for (auto &a : nums) {
            res.push_back(a[1]);
        }
        return res;
    }
};

再來看一種寫法，這里就主要是把自定義排序方式，和統計1的個數都拆分成了單獨的子函數，還有就是統計1的個數的時候和前面的解法稍有些不同。這里采用的是 num & (num - 1)，這個操作實際上是快速移除右起第一個1的方法，可以舉個例子來看，比如 101 & 100 = 100 這里的 101 就變成了 100，最右邊的1被移除了?；蛘?1100 & 1011 = 1000，1100 變成了 1000，右起第一個1被移除了，這樣的話每次操作必定會移除一個1，則計算器可以自增1，循環退出條件也是當數字變為0了退出。這樣計算的效率能比之前一位一位檢查的高一些，參見代碼如下：

解法二：

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), compare);
        return arr;
    }
    static bool compare(int a, int b) {
        int cntA = cntOne(a), cntB = cntOne(b);
        return cntA == cntB ? (a < b) : (cntA < cntB);
    }
    static int cntOne(int num) {
        int cnt = 0;
        while (num > 0) {
            num = num & (num - 1);
            ++cnt;
        }
        return cnt;
    }
};

再來看一種利用 C++ 自帶統計1的個數的方法，用到了 __builtin_popcount 這個函數，當然如果面試中你這么玩的話，估計過不了，只是放上來秀一下而已，大家還是老老實實用前面的解法吧，參見代碼如下：

解法三：

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [](int &a, int &b) {
            int cntA = __builtin_popcount(a), cntB = __builtin_popcount(b);
            return cntA == cntB ? (a < b) : (cntA < cntB);
        });
        return arr;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1355

類似題目：

Find Subsequence of Length K With the Largest Sum

參考資料：

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

https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/solutions/758095/cpp-simple-solution-using-self-defined-comparator/

https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/solutions/517017/c-in-place-sort-popcount/

LeetCode All in One 題目講解匯總(持續更新中...)