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) —
推荐阅读:关于元宵节的作文500字 总是瞬间让幸福盈满心中 美丽的珠海作文 留一点休息给自己作文 看图写话 补课 桓昕昱|小学作文 家乡的如意湖作文 三八妇女节珍贵的礼物作文 中国魂,民族魂! 我的娃打架?小打小闹? 植树问题例题解答
- 评论列表
-
- 添加评论