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

2021-04-26 HGNULB 约 10 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

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

题意分析

给定一个整数数组 arr，要求把它重新排列：二进制表示中 1 的个数少的排在前面；如果两个数二进制中 1 的个数一样多，则按数值本身从小到大排。返回排序后的数组。

这道题本质上没有任何算法难点，它考的是两件很基础但很容易写错的事：怎么把「1 的个数」这个派生量算出来，以及怎么把「主关键字 + 次关键字」这个复合序正确地表达成一个比较函数。题面直接把排序规则写成两句话，这就是一个明确的信号：需要的是自定义比较，而不是某种巧妙的构造。

约束里有两个数字值得读一下。数组长度不超过 500，说明对时间完全没有压力，$O(n \log n)$ 甚至 $O(n^2)$ 都能过，不要在这里过度优化；元素范围是 $[0, 10^4]$，也就是最多 14 个二进制位，所以「1 的个数」这个值只可能落在 $[0, 14]$ 这个极小的区间里——这一点后面会决定次关键字的写法是否安全。

边界主要有三处。第一，数组里可以出现 0，它的 1 的个数是 0，永远排在最前面，写统计函数时必须保证 0 不会让循环出问题。第二，数组里可以有重复元素，两个相等的数在两个关键字上都相同，比较函数必须能返回「相等」而不是随便返回一个方向。第三，元素全部非负，所以不用担心补码高位一片 1 的情况——如果题目允许负数，Java 里 num != 0 配合 num &= num - 1 依然正确，但直觉上会以为要处理符号位。

解法：自定义排序

核心思路

先把「1 的个数」这个派生量的算法定下来。最朴素的写法是逐位右移，每次看最低位是不是 1，循环 $O(\log U)$ 次，其中 $U$ 是数值上界。更好的写法是 Brian Kernighan 算法：num &= num - 1。它的原理是，num - 1 会把 num 最低位的那个 1 变成 0、并把它右边所有的 0 变成 1，于是 num & (num - 1) 恰好抹掉了最低位的那一个 1，其余位不受影响。所以循环次数等于 1 的个数，而不是总位数，对稀疏的数字快得多，写起来也只有两行。

再把排序规则形式化。题目要的是字典序意义下的双关键字升序：定义 key(x) = (popcount(x), x)，答案就是把 arr 按 key 从小到大排序。比较函数的语义必须是「先比第一维，第一维分不出胜负才比第二维」，也就是必须显式写出 if (countA != countB) return countA - countB; 这个短路分支，然后才 return a - b;。少写这个分支、或者把两维的比较顺序调换，得到的都是另一个题目的答案。

这里有一个可以顺带说给面试官听的观察：因为 popcount(x) ≤ 14 而 x ≤ 10^4，两个关键字可以压成一个整数 popcount(x) * 100000 + x，然后按单关键字排序，效果完全一样。这在需要把双关键字塞进一个 int[] 或者语言不方便写比较器时很有用。本题直接写比较器更直观，所以保留比较器写法，但知道有这条退路是加分项。

最后是语言层面的一个坑，也是本题在 Java 里唯一真正会卡住人的地方：Arrays.sort(int[]) 没有接受 Comparator 的重载，因为 Comparator<T> 需要引用类型。所以必须先把 int[] 装箱成 Integer[]，排完序再拆箱写回原数组。Go 没有这个限制，sort.Slice 直接对底层切片按下标交换，因此 Go 版本可以原地排序、不需要任何中间数组。

解题步骤

把原数组装箱成 Integer[]：逐个赋值即可。这一步不是可有可无的样板，而是因为 Java 的比较器只能作用在引用类型数组上；如果直接对 int[] 调用 Arrays.sort，只能得到默认的数值升序。

实现 countBits：用 while (num != 0) { num &= num - 1; count++; }。循环条件用 num != 0 而不是 num > 0，这样即使将来题目放开负数也依然正确；num 是按值传入的副本，直接修改它不会影响调用方。

写比较器的第一维：算出两数各自的 1 的个数，不相等就返回它们的差。这里返回差值是安全的，因为两个计数都在 $[0, 14]$ 内，相减绝不会溢出。

写比较器的第二维：第一维相等时返回 a - b。同样安全，因为元素都在 $[0, 10^4]$ 内。如果题目的取值范围放大到 int 全域，这里必须换成 Integer.compare(a, b)，否则 a - b 会溢出并给出反向的比较结果——这是面试官很爱追问的一点。

把结果写回 int[] 并返回：题目要求返回 int[]，逐个拆箱写回原数组即可，省掉再开一个数组。

以 arr = [0, 1, 2, 3, 4, 5, 6, 7, 8] 走一遍。先算每个数的 1 的个数：0 → 0，1 → 1，2(10) → 1，4(100) → 1，8(1000) → 1，3(11) → 2，5(101) → 2，6(110) → 2，7(111) → 3。

按第一维分组后是：计数 0 组 {0}，计数 1 组 {1, 2, 4, 8}，计数 2 组 {3, 5, 6}，计数 3 组 {7}。组内再按数值升序排，各组本身已经有序，拼接得到 [0, 1, 2, 4, 8, 3, 5, 6, 7]。

单独看 countBits(7) 的执行过程：num = 7 (111)，第一轮 7 & 6 = 6 (110)，count = 1；第二轮 6 & 5 = 4 (100)，count = 2；第三轮 4 & 3 = 0，count = 3；num 归零退出，返回 3。三轮循环对应三个 1，而不是对应 14 个二进制位。

如果漏掉比较器里的第一维分支、只写 return a - b，上面的输入会原样返回 [0,1,2,3,4,5,6,7,8]；如果两维顺序写反、先比数值再比计数，第二维永远不会被触发（数值互不相同），结果同样是纯数值升序。这两个错误的输出长得很像，都很有迷惑性。

代码实现

class Solution {
    public int[] sortByBits(int[] arr) {
        // Comparator 只能作用于引用类型数组，int[] 没有带比较器的 sort 重载，先装箱。
        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);
            // 主关键字：1 的个数；两者都不超过 14，相减不会溢出。
            if (countA != countB) {
                return countA - countB;
            }
            // 主关键字相同才比次关键字：数值本身，上界 10^4 同样不会溢出。
            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) {
            // Brian Kernighan：num - 1 会翻转最低位的 1 及其右侧全部 0，与运算后恰好抹掉一个 1。
            num &= num - 1;
            count++;
        }

        return count;
    }
}

func sortByBits(arr []int) []int {
    // Go 的 sort.Slice 按下标交换底层数组，可以直接原地排序，无需装箱或额外数组。
    sort.Slice(arr, func(i int, j int) bool {
        countI := countBits(arr[i])
        countJ := countBits(arr[j])
        // 主关键字：1 的个数；只有它分不出胜负时才看数值。
        if countI != countJ {
            return countI < countJ
        }
        return arr[i] < arr[j]
    })

    return arr
}

func countBits(num int) int {
    count := 0
    for num != 0 {
        // 每次消掉最低位的一个 1，循环次数等于 1 的个数而非总位数。
        num &= num - 1
        count++
    }

    return count
}

复杂度分析

时间复杂度：$O(n \log n \cdot \log U)$，其中 $n$ 是数组长度、$U$ 是元素上界。排序本身是 $O(n \log n)$ 次比较，而每次比较都要现场计算两个数的 1 的个数，单次 $O(\log U)$。如果在排序前先把每个元素的 1 的个数预处理进一个数组、比较时直接查表，可以降到 $O(n \log n + n \log U)$；本题 $n \le 500$，两者没有实际差别。

空间复杂度：Java 版是 $O(n)$，代价来自装箱出来的 Integer[]（外加 Arrays.sort 对引用类型使用 TimSort 所需的辅助空间）；Go 版是 $O(\log n)$，sort.Slice 原地快排只消耗递归栈。

关键点总结

双关键字排序的标准骨架是「主关键字不等就直接返回主关键字的比较结果，相等才落到次关键字」，短路分支必须显式写出来，这个模板可以原样迁移到任何多关键字排序题。

num &= num - 1 是 popcount 的通用手法，循环次数等于 1 的个数；理解它的关键是「减一会借位到最低位的那个 1」，面试时能讲清这句原理比背下写法更重要。

比较器里用相减代替 compare 是有前提的——两个操作数的差必须落在 int 范围内。本题因为值域小而安全，但工程代码和值域未知的题目里应当无条件使用 Integer.compare。

当关键字个数有限且取值范围可控时，可以把多关键字编码成单个整数（这里是 popcount * 100000 + x）再单关键字排序，这是把复合序压平的通用技巧。

Java 的基本类型数组无法直接使用比较器，这是语言层面的硬限制；面试中被问到 int[] 怎么自定义排序，正确答案就是装箱、或者自己手写排序、或者用编码压平的方式。

易错点总结

比较器只写 return a - b，漏掉计数分支：输入 [0,1,2,3,4,5,6,7,8] 会原样返回 [0,1,2,3,4,5,6,7,8]，而正确答案是 [0,1,2,4,8,3,5,6,7]。

两个关键字的顺序写反，先比数值再比计数：因为数值互不相同时次关键字永远不会被触发，输出退化成纯数值升序，和上一条的错误输出完全一样，很难通过肉眼分辨。

直接对 int[] 调用 Arrays.sort(arr, cmp)：编译不通过；如果写成 Arrays.sort(arr) 则编译通过但结果是普通升序，输入 [1024, 512, 3] 会得到 [3, 512, 1024]，而正确答案是 [512, 1024, 3]。

countBits 的循环条件写成 num > 0 且题目放开负数：-1 的补码全 1，num > 0 直接为假，返回 0，这个数会被错误地排到最前面。用 num != 0 可以避免。

把 num &= num - 1 写成 num &= num + 1：对 num = 7 会得到 7 & 8 = 0，一轮就退出并返回 1，所有含多个 1 的数都会被低估。

忘记把排序结果写回 int[] 就返回原数组：Integer[] 排好了序，但返回的 arr 还是原始顺序，输出完全没变化。

比较器返回布尔值或返回 true/false 语义的整数：Java 的 Comparator 要求返回负数/零/正数三态，只返回 0 和 1 会让 TimSort 认为所有元素「不小于」彼此，触发 Comparison method violates its general contract! 异常。

值域放大后仍用 a - b：若数组含 Integer.MIN_VALUE 和一个正数，a - b 溢出后符号反转，排序结果错乱且不报错，属于最难排查的一类 bug。

在 Go 里用 sort.Slice 时把闭包写成比较 i 和 j 而不是 arr[i] 和 arr[j]：sort.Slice 的回调收到的是下标，忘记取值会得到「按下标升序」也就是原样返回。

相似题目

题目	难度	考察点
191. 位1的个数	简单	只求单个数的 popcount，是本题 `countBits` 的独立版本
338. 比特位计数	简单	批量求 `0..n` 的 popcount，用 `dp[i] = dp[i>>1] + (i&1)` 递推推表
LCR 003. 比特位计数	简单	与 338 同题，可直接套用同一递推
1122. 数组的相对排序	简单	关键字由另一个数组给定的排名决定，值域小时用计数桶比比较器更快
1636. 按照频率将数组升序排序	简单	同样双关键字，但主关键字频次升序、次关键字数值降序，两维方向相反
905. 按奇偶排序数组	简单	关键字只有两种取值，双指针原地划分即可，根本不需要排序
791. 自定义字符串排序	中等	关键字来自给定顺序串的位置映射，需要先建立字符到序号的表
461. 汉明距离	简单	先异或再数 1，把 popcount 用在两数差异统计而非排序上