給你一個整數數組 arr 。請你将數組中的元素按照其二進制表示中數字 1 的數目升序排序。
如果存在多個數字二進制中 1 的數目相同,則必須将它們按照數值大小升序排列。
請你傳回排序後的數組。
示例 1:
輸入:arr = [0,1,2,3,4,5,6,7,8]
輸出:[0,1,2,4,8,3,5,6,7]
解釋:[0] 是唯一一個有 0 個 1 的數。
[1,2,4,8] 都有 1 個 1 。
[3,5,6] 有 2 個 1 。
[7] 有 3 個 1 。
按照 1 的個數排序得到的結果數組為 [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]
解釋:數組中所有整數二進制下都隻有 1 個 1 ,是以你需要按照數值大小将它們排序。
示例 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
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
暴力排序。。。
bool cmp1(int a,int b){
int na=0,nb=0;
int aa=a,bb=b;
while(a>0){
na+=a%2;
a=a/2;
}
while(b>0){
nb+=b%2;
b=b/2;
}
if(na!=nb){
cout<<na<<nb<<" "<<a<<" "<<b<<" "<<endl;
return na<nb;
}else {
return aa<bb;
}
}
class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
sort(arr.begin(),arr.end(),cmp1);
return arr;
}
};
複制