二进制排序题怎么做
2025-05-02 12:38:55
起步向前走
已认证
已认证起步向前走为您分享以下优质知识
二进制排序题的核心在于根据数字的二进制表示中1的个数进行排序，当1的个数相同时则按数值大小排序。以下是解决这类问题的通用方法和示例：
一、解题思路
计算二进制中1的个数
对每个数字进行二进制转换，并统计其中1的个数。可以通过位运算高效实现，例如使用 `n & （n - 1）` 操作快速消除最低位的1。
排序规则
- 首先按1的个数升序排列；
- 若1的个数相同，则按数值大小升序排列。
二、实现步骤
统计1的个数的函数
使用位运算优化计算效率：
```python
def count_ones(n: int) ->
int:
count = 0
while n:
n &= n - 1
count += 1
return count
```
排序函数
使用稳定排序算法（如Python的`sorted`函数），并提供自定义排序键：
```python
def sort_by_bits(arr: List[int]) ->
List[int]:
return sorted(arr, key=lambda x: (count_ones(x), x))
```
完整示例
结合上述步骤，完整代码如下：
```python
def count_ones(n: int) ->
int:
count = 0
while n:
n &= n - 1
count += 1
return count
def sort_by_bits(arr: List[int]) ->
List[int]:
return sorted(arr, key=lambda x: (count_ones(x), x))
示例
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]
print(sort_by_bits(arr)) 输出: [0, 1, 2, 4, 8, 3, 5, 6, 7]
```
三、注意事项
数据范围
根据题目限制（如LeetCode第1356题），数组长度和数值范围需注意，避免溢出。
效率优化
- 位运算方法比字符串转换更高效；
- 若使用其他语言，可利用内置排序函数并自定义比较器。
四、扩展应用
降序排序：
将比较函数中的 `x` 改为 `-x`；
其他排序规则：如按末尾0的个数排序，可结合 `n & -n` 统计。
通过以上方法，可高效解决二进制排序问题。
