二进制排序题怎么做的啊
2025-05-10 03:38:30
考官何老师
已认证
已认证考官何老师为您分享以下优质知识
二进制排序题的核心思路是通过统计每个数字的二进制中“1”的数量进行排序，若数量相同则按数值大小排序。以下是具体步骤和实现方法：
一、核心步骤
统计二进制中1的个数
将每个数字转换为二进制字符串，统计其中“1”的数量。例如，数字5的二进制为`101`，包含2个“1”。
多条件排序
- 首先按“1”的数量升序排列；
- 若数量相同，则按数值大小升序排列。
二、实现方法
暴力法（推荐）
- 遍历数组，对每个数字计算二进制中“1”的个数；
- 使用内置排序函数（如Java的`Collections.sort`），自定义比较器实现多条件排序。
优化方法（哈希表+排序）
- 使用哈希表（如Java的`HashMap`）将数字映射到其“1”的数量；
- 先按“1”的数量排序，再按数值大小排序，最后生成结果数组。
三、代码示例（仓颉语言）
```仓颉
fun sortByBits(arr: Array): Array {
// 计算每个数字的二进制中1的个数
var bitCounts = Array(arr.length) { 0 }
for (i in 0 until arr.length) {
bitCounts[i] = functoBinary(arr[i]).count('1')
}
// 按1的个数和数值大小排序
arr.sortWith { a, b ->
if (bitCounts[a] != bitCounts[b]) {
bitCounts[a] - bitCounts[b]
} else {
a - b
}
}
return arr
}
fun functoBinary(n: Int): String {
var binary = ""
var num = n
while (num != 0) {
binary = (num % 2).toString() + binary
num /= 2
}
return binary
}
```
四、注意事项
效率：
暴力法时间复杂度为O（n log n），哈希表+排序法在统计阶段为O（n），排序阶段仍为O（n log n），整体效率较高；
边界情况：需处理全0、全1等特殊情况，确保排序规则正确。
通过以上方法，可高效解决二进制排序问题。
