How do I approach sorting by the number of 1 bits in the binary representation?

Start by counting the number of 1 bits in each number using bitwise operations. Then, sort the numbers using these counts, with ties broken by value.

What is the most efficient way to count the number of 1 bits?

The most efficient way is to use the built-in bitwise operations like n & (n - 1) to count bits, which operates in constant time per number.

How does the time complexity of sorting affect the solution?

Sorting dominates the time complexity, resulting in O(n log n). The bit counting step is O(1) per number, so it doesn't impact the overall complexity significantly.

What if two integers have the same number of 1 bits?

If two integers have the same number of 1 bits, they are sorted by their value in ascending order.

Can this approach be applied to other problems involving sorting based on bit manipulation?

Yes, the approach can be generalized to any problem where sorting is based on a custom condition, such as the number of bits set to 1 or other bit-level properties.

#1356

Easy

auto_awesome数组·结合·位运算·操作

LeetCode 题解工作台

根据数字二进制下 1 的数目排序

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。请你返回排序后的数组。示例 1：输入： arr = [0,1,2,3,4,5,6,7,8] 输出： [0,1,2,4,8,3,…

数组位运算排序计数

题目描述

给你一个整数数组 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

lightbulb

解题思路

方法一：自定义排序

我们将数组 $arr$ 按照题目要求排序，即按照二进制表示中数字 $1$ 的数目升序排序，如果存在多个数字二进制中 $1$ 的数目相同，则必须将它们按照数值大小升序排列。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $arr$ 的长度。

1

2

3

4

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        return sorted(arr, key=lambda x: (x.bit_count(), x))

speed

复杂度分析

指标	值
时间	O(n \cdot \log{}n)
空间	O(\log n)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate understands the efficient use of bitwise operations for counting 1 bits.
question_mark
Evaluate how well the candidate handles sorting with a custom key function.
question_mark
Assess whether the candidate can explain the time and space complexities of their approach.

warning

常见陷阱

外企场景

error
Failing to correctly handle tie cases where two numbers have the same number of 1 bits.
error
Using inefficient bit-counting methods that result in slower performance for larger arrays.
error
Not understanding how to leverage Python’s sorting key function, leading to unnecessary complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to sort by the number of 0 bits instead of 1 bits.
arrow_right_alt
Extend the problem to work with negative integers and their binary representations.
arrow_right_alt
Change the sorting order, sorting by the number of 1 bits in descending order.

help

常见问题

外企场景

继续练习

#1366 通过投票对团队排名 #1481 不同整数的最少数目 #1090 受标签影响的最大值