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

发表于 更新于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，1356. Sort Integers by The Number of 1 Bits

先看题目描述

BWjgyQ.png

大意就是给定一个数组，让我们对其排序，排序规则是比较两个数的二进制表示下数字 1 的数目，小的在前面，若 1 的数目相同，则本身数值小的在前面

算法和思路

对数组的排序部分，只需调用系统自带的排序函数，然后改写下排序规则即可，那么重点就在于怎么求数字在二进制表示下数字 1 的个数

我们定义 bits[i] 为数字 i 在二进制表示下数字 1 的个数，则有如下递推式：bits[i] = bits[i >> 1] + (i & 1)​

所以先线性预处理 bits 数组然后去排序即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

class Solution {
    public int[] sortByBits(int[] arr) {
        int len = arr.length;
        List<Integer> nums = new ArrayList<>();
        int[] res = new int[len];
        for (int num : arr) {
            nums.add(num);
        }
        int[] bits = new int[10001];
        for (int i = 0; i <= 10000; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        Collections.sort(nums, new Comparator<Integer>() {
            @Override
            public int compare(Integer x, Integer y) {
                if (bits[x] != bits[y]) {
                    return bits[x] - bits[y];
                } else {
                    return x - y;
                }
            }
        });
        for (int i = 0; i < len; i++) {
            res[i] = nums.get(i);
        }
        return res;
    }
}

这个代码中，我感觉用递推式 bits[i] = bits[i >> 1] + (i & 1) 先线性预处理 bits 数组来求数字 i 在二进制表示下数字 1 的数目很巧妙，需要注意的是 (i & 1) 外层的括号不能去掉，不然就会出问题，这个应该和运算符的优先级有关；还有就是直到现在才知道 collections.sort() 函数可以自定义排序规则，重写 Comparator 接口中的 compare 方法即可，大致就是经 compare 方法比较后，若返回值大于 0，则第一个参数放后面，否则的话第一个参数放前面，印象中 python 也有类似函数

后来又去看击败时间击败 100% 的代码，发现 java 实现了一个 Integer.bitCount() 方法，可以获取数字转化为二进制后其中数字 1 的数目，尝试去看这个方法的源码，但是并没有看懂…另外别人实现代码的这个排序方式也很巧妙，是采用赋予转化为二进制后其中数字 1 的数目和自身数值不同系数的方式来进行排序。别人一开始用的是 100000，我改成了 10001，因为题目说了数字范围为 0-10000，所以只要用个比 10000 大的数字就行。另外还发现了有趣的一点，如果采用的是 for(int num : ans) 这种 for each 循环，ans 并不会改变，应该是因为 ans[i] 这种索引的形式才会改变 ans 数组吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] sortByBits(int[] arr) {
        int[] ans = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            //Integer.bitCount(arr[i])转化为二进制一的数量
            ans[i] = Integer.bitCount(arr[i]) * 10001 + arr[i];
        }
        Arrays.sort(ans);
        for (int i = 0; i < ans.length; i++) {
            ans[i] = ans[i] % 10001;
        }
        return ans;
    }
}

另外 Integer.bitCount() 方法的源码如下，这个方法只可以用于 32 位的整数

1
2
3
4
5
6
7
8
9
public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }