LeetCode 1356. 根据数字二进制下 1 的数目排序
题目描述
题意分析
将数组按二进制中 1 的数量升序排列，数量相同时再按数值升序排列。数组中的每次出现都要保留，不能将重复数字去重。
解法：自定义排序
核心思路
[!blue]
将每个数的排序键看成
(1 的数量, 原数值)。比较两个元素时，第一项不相等就由它决定先后；只有第一项相等，才比较第二项。这种按优先级比较的规则正好对应题目的两层排序要求。
countBits用num &= num - 1统计 1。减一会把最低的 1 变为 0、它右侧的 0 变为 1，再与原数相与，便只清除了这一个 1。每轮计数加一，直到num归零，循环次数就是所需数量；输入 0 则直接返回 0。函数修改的是参数副本，不会改变数组中的原数值。Java 的
int[]排序接口不能接收这个自定义比较器，因此先复制到Integer[]，按两层规则排序，再写回原数组。Go 的sort.Slice将当前待比较的下标传给回调，应读取arr[i]、arr[j]来比较，不能把下标本身当成数字。
解题步骤
- 实现统计一的数量。
- 按一的数量与原值两层规则排序。
- Java 将排序后的装箱结果写回原数组。
代码实现
class Solution {
public int[] sortByBits(int[] arr) {
// 装箱后才能使用这个数组自定义比较器，排序结果最后写回原数组。
Integer[] nums = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) {
nums[i] = arr[i];
}
Arrays.sort(
nums,
(a, b) -> {
int countA = countBits(a);
int countB = countBits(b);
// 先按一的数量排序，相同时才比较原值。
if (countA != countB) {
return countA - countB;
}
return a - b;
});
for (int i = 0; i < arr.length; i++) {
// 将已经排序的装箱值还原到返回的基本类型数组。
arr[i] = nums[i];
}
return arr;
}
private int countBits(int num) {
int count = 0;
while (num != 0) {
// 每次消去最低位的一，直到全部消完。
num &= num - 1;
count++;
}
return count;
}
}
import "sort"
func sortByBits(arr []int) []int {
sort.Slice(arr, func(i int, j int) bool {
countI := countBits(arr[i])
countJ := countBits(arr[j])
// 先按一的数量排序，相同时才比较原值。
if countI != countJ {
return countI < countJ
}
return arr[i] < arr[j]
})
return arr
}
func countBits(num int) int {
count := 0
for num != 0 {
// 每次消去最低位的一，直到全部消完。
num &= num - 1
count++
}
return count
}
复杂度分析
- 时间复杂度：$O(n\log(n+1)\,W)$，其中 $n$ 为数组长度，$W$ 为最多参与统计的位数。每次比较都重新统计两数的 1，本题数值不超过 $10^4$，$W\le14$。
- 空间复杂度：Java 为 $O(n)$，Go 排序栈为 $O(\log(n+1))$。
关键点总结
[!green]
- 零的一数为零，相同数字也要保留全部副本。
- 只有第一关键字相同才使用第二关键字。
- 题面数值范围为 $[0,10^4]$，Java 比较器中的数值差和位数差都不会溢出。
易错点总结
[!yellow]
- 只按数值排序会忽略 1 的数量这一优先级；只按 1 的数量排序又无法保证并列时的数值顺序。
- 比较回调拿下标当元素值，会失去实际排序键。
- 消位写成与 num+1 做与运算，不能保证每次消去一个一。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 191. 位1的个数 | 简单 | 位1的计数是第一排序键，相同时再按原数值升序比较。 |
| 338. 比特位计数 | 简单 | 若值域较小，可预计算每个数的位计数，再用于排序键，减少重复统计。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！