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

解题思路

1. 定义一个辅助函数 countBits，利用位运算计算每个数字的二进制表示中 1 的个数。

   • 方法是将数字不断右移 (n >>= 1)，同时检查最低位是否为 1 (n & 1)。

2. 将数组 arr 映射为 [countBits(n), n] 的形式。

3. 使用自定义排序规则排序：

   • 若 1 的个数不同，按 1 的个数排序；
   • 若相同，按数字大小排序。

4. 提取排序后的数字并返回结果。

复杂度分析

• 时间复杂度：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	判断一个数组是否可以变为有序	[✓]	位运算 数组 排序	🟠	🀄️ 🔗