How to Sort Integers by The Number of 1 Bits?
- 时间:2020-09-10 13:27:27
- 分类:网络文摘
- 阅读:92 次
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) —
推荐阅读:过程胜过结局作文800字 新之三下乡第一天 过三八妇女节有感300字 吹鸡毛作文300字 神奇的云作文400字 我的脚印边,是你的脚印作文 心情日记的作文 打陀螺作文400字 难忘国庆节作文500字 等底等高的圆柱与圆锥体积之和
- 评论列表
-
- 添加评论