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

難度：簡單

給你一個整數(shù)數(shù)組 arr 。請你將數(shù)組中的元素按照其二進制表示中數(shù)字 1 的數(shù)目升序排序。

如果存在多個數(shù)字二進制中 1 的數(shù)目相同，則必須將它們按照數(shù)值大小升序排列。

請你返回排序后的數(shù)組。

示例 1：

輸入：arr = [0,1,2,3,4,5,6,7,8]
輸出：[0,1,2,4,8,3,5,6,7]
解釋：[0] 是唯一一個有 0 個 1 的數(shù)。
[1,2,4,8] 都有 1 個 1 。
[3,5,6] 有 2 個 1 。
[7] 有 3 個 1 。
按照 1 的個數(shù)排序得到的結(jié)果數(shù)組為 [0,1,2,4,8,3,5,6,7]

示例 2：

輸入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
輸出：[1,2,4,8,16,32,64,128,256,512,1024]
解釋：數(shù)組中所有整數(shù)二進制下都只有 1 個 1 ，所以你需要按照數(shù)值大小將它們排序。

示例 3：

輸入：arr = [10000,10000]
輸出：[10000,10000]

示例 4：

輸入：arr = [2,3,5,7,11,13,17,19]
輸出：[2,3,5,17,7,11,13,19]

示例 5：

輸入：arr = [10,100,1000,10000]
輸出：[10,100,10000,1000]

提示：

• $1<=arr.length<=500$
• $0<=arr[i]<=10^4$

??思路：位運算

對位運算基本操作還不太懂的小伙伴可以看我另一篇博客：一篇文章搞懂位運算!!!

法一：仿函數(shù) + 位運算

• 使用位運算，去除最低的那一位 1，來統(tǒng)計 1 的個數(shù)；
• 然后根據(jù)仿函數(shù)的定義，重新定義比較函數(shù) 4cmp;
• 最后使用 sort 函數(shù)重新排序，并使用我們自己定義的比較函數(shù)。

法二：數(shù)學(xué) + 位運算

• 由題目提示，$0<=arr[i]<=10^4$，所以 arr[i] 二進制1不超過 14個，占十進制中的兩位；且先比較二進制中 1 的個數(shù)，所以個數(shù)可以占高位，乘以 100000；

• 若1 的個數(shù)相同，則比較 arr[i]，即最后再加上 arr[i];

• 然后用 sort 進行排序，最后再取余，即為答案；

??代碼：(C++、Java)

法一：仿函數(shù) + 位運算
C++

class Solution {
private:
    static int bitCount(int num){
        int count = 0;
        while(num > 0){
            num &= (num - 1);
            count++;
        }
        return count;
    }
    static bool cmp(int a, int b){
        int bitA = bitCount(a);
        int bitB = bitCount(b);
        if(bitA == bitB) return a < b;
        return bitA < bitB;
    }
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), cmp);
        return arr;
    }
};

法二：數(shù)學(xué) + 位運算

C++

class Solution {
private:
    static int bitCount(int num){
        int count = 0;
        while(num > 0){
            num &= (num - 1);
            count++;
        }
        return count;
    }
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<int> map(arr.size());
        for(int i = 0; i < arr.size(); i++){
            map[i] = bitCount(arr[i]) * 100000 + arr[i];
        }
        sort(map.begin(), map.end());
        for(int i = 0; i < map.size(); i++){
            map[i] %= 100000;
        }
        return map;
    }
};

Java

class Solution {
    public int[] sortByBits(int[] arr) {
        int[] map = new int[arr.length];
        for(int i = 0; i < arr.length; i++){
            map[i] = Integer.bitCount(arr[i]) * 100000 + arr[i];
        }
        Arrays.sort(map);
        for(int i = 0; i < map.length; i++){
            map[i] %= 100000;
        }
        return map;
    }
}

?? 運行結(jié)果：

?? 復(fù)雜度分析：

• 時間復(fù)雜度：$O(nlogn)$，其中 n 為數(shù)組的長度，。
• 空間復(fù)雜度：$O(1)$，法二為 $O(n)$ 。

題目來源：力扣。

放棄一件事很容易，每天能堅持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁 / CSDN—力扣專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-524255.html

注： 如有不足，歡迎指正！

到了這里，關(guān)于(位運算) 1356. 根據(jù)數(shù)字二進制下 1 的數(shù)目排序 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！