How to Sort Integers by The Number of 1 Bits?
- 时间:2020-09-10 13:27:27
- 分类:网络文摘
- 阅读:78 次
Given an integer array arr. You have to 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 sorted array.
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.Example 3:
Input: arr = [10000,10000]
Output: [10000,10000]Example 4:
Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]Example 5:
Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]Constraints:
1 <= arr.length <= 500
0 <= arr[i] <= 10^4Hints:
Simulate the problem. Count the number of 1’s in the binary representation of each integer.
Sort by the number of 1’s ascending and by the value in case of tie.
Count the Number of Set Bits
In order to solve the problem, we need to be able to count the number of ‘1’s in a number’s binary representation. A faster approach is detailed in here using the bit tweaks.
A classic approach using a loop would be:
1 2 3 4 5 6 7 8 | int bitSet(int n) { int count = 0; while (n > 0) { count += (n & 1); // the rightmost bit n >>= 1; // shifting 1 to the right } return count; } |
int bitSet(int n) { int count = 0; while (n > 0) { count += (n & 1); // the rightmost bit n >>= 1; // shifting 1 to the right } return count; }
In C++, we can use the built-in compiler intrinsic __builtin_popcount or the std::bitset class.
Sorting the Numbers using Custom Comparator
Then, we can just use std::sort() with a customize comparator. See below C++ implementations:
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public: vector<int> sortByBits(vector<int>& arr) { sort(begin(arr), end(arr), [](auto &a, auto &b) { int aa = __builtin_popcount(a); int bb = __builtin_popcount(b); return aa < bb || ((aa == bb) && (a < b)); }); return arr; } }; |
class Solution { public: vector<int> sortByBits(vector<int>& arr) { sort(begin(arr), end(arr), [](auto &a, auto &b) { int aa = __builtin_popcount(a); int bb = __builtin_popcount(b); return aa < bb || ((aa == bb) && (a < b)); }); return arr; } };
And:
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public: vector<int> sortByBits(vector<int>& arr) { sort(begin(arr), end(arr), [](auto &a, auto &b) { int aa = std::bitset<32>(a).count(); int bb = std::bitset<32>(b).count(); return aa < bb || ((aa == bb) && (a < b)); }); return arr; } }; |
class Solution { public: vector<int> sortByBits(vector<int>& arr) { sort(begin(arr), end(arr), [](auto &a, auto &b) { int aa = std::bitset<32>(a).count(); int bb = std::bitset<32>(b).count(); return aa < bb || ((aa == bb) && (a < b)); }); return arr; } };
Please note that the std::sort() algorithm takes O(NLogN) time complexity.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:网站内部优化细节流程(纯白帽SEO) 网站安全防止被黑客攻击的办法 我在落伍的那几年:一个个人站长的回忆录 给哪些网站暂时赚不到钱的站长鼓鼓劲 个人站长 建设网站贵在坚持 网站站长赚钱的6大好用的途径 整理6款站长赚钱方法 希望对你有所帮助 个人站长们常见的很多个网站盈利模式总结 春季饮食宜润肺,常吃炖梨既滋润又养人,口感甜香味道美 这道小学应用题比较难,解题关键是求相遇时间
- 评论列表
-
- 添加评论