根据数字二进制中1的个数排序(LC1356)
哪些公司问过
鲲鹏华清1
答案要点
- 排序规则:先按二进制 1 的个数升序,再按数值升序
- 统计 1 的个数可用内置 popcount、x&(x−1) 或递推 bits[i]=bits[i>>1]+(i&1)
- 双关键字已构成全序,结果不依赖稳定性
- 时间复杂度 O(n log n)
易错点
- 只按 1 的个数排序,忘了相同个数时按数值排序
- 用 x>>1 循环统计负数时在有符号右移下死循环
- 编码键时乘数取得太小导致关键字冲突
面试官常见追问
- x&(x−1) 为什么能消去最低位的 1?
- 负数怎么处理?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场