1356. 根据数字二进制下 1 的数目排序
1356. 根据数字二进制下 1 的数目排序
🟢 🔖 位运算
数组
计数
排序
🔗 力扣
LeetCode
题目
You are given an integer array arr
. 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 array after sorting it.
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.
Constraints:
1 <= arr.length <= 500
0 <= arr[i] <= 10^4
题目大意
给你一个整数数组 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
解题思路
定义一个辅助函数
countBits
,利用位运算计算每个数字的二进制表示中1
的个数。- 方法是将数字不断右移 (
n >>= 1
),同时检查最低位是否为1
(n & 1
)。
- 方法是将数字不断右移 (
将数组
arr
映射为[countBits(n), n]
的形式。使用自定义排序规则排序:
- 若
1
的个数不同,按1
的个数排序; - 若相同,按数字大小排序。
- 若
提取排序后的数字并返回结果。
复杂度分析
- 时间复杂度:
O(n log k + n log n)
- 计算
1
的个数:对每个数字调用countBits
,复杂度为O(log k)
,其中k
是数组中最大数字。 - 排序:
O(n log n)
,其中n
是数组长度。 - 总复杂度为
O(n log k + n log n)
。
- 计算
- 空间复杂度:
O(n)
,映射和排序的辅助数组占用O(n)
空间。
代码
/**
* @param {number[]} arr
* @return {number[]}
*/
var sortByBits = function (arr) {
const countBits = (n) => {
let count = 0;
while (n > 0) {
count += n & 1; // 检查最低位是否为 1
n >>= 1; // 右移一位
}
return count;
};
return arr
.map((n) => [countBits(n), n]) // 映射为 [1 的个数, 数字]
.sort((a, b) => {
if (a[0] === b[0]) return a[1] - b[1]; // 按数字大小排序
return a[0] - b[0]; // 按 1 的个数排序
})
.map(([bits, n]) => n); // 提取排序后的数字
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2099 | 找到和最大的长度为 K 的子序列 | [✓] | 数组 哈希表 排序 1+ | 🟢 | 🀄️ 🔗 |
3011 | 判断一个数组是否可以变为有序 | [✓] | 位运算 数组 排序 | 🟠 | 🀄️ 🔗 |