leetcode 2026-02-25 每日一练 - 根据数字二进制下 1 的数目排序

Austoin2026-02-252026-02-25

题目描述

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

给你一个整数数组 arr。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

解题思路

这道题的核心是自定义排序规则：

首先统计每个数字二进制表示中 1 的个数
按照 1 的个数升序排序（个数少的排前面）
如果 1 的个数相同，则按照数值大小升序排序

Go 语言提供了 bits.OnesCount() 函数来统计二进制中 1 的个数，非常方便。

代码实现

方法一：冒泡排序

func sortByBits(arr []int) []int {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-1-i; j++ {
            cntA := bits.OnesCount(uint(arr[j]))
            cntB := bits.OnesCount(uint(arr[j+1]))

            if cntA > cntB || (cntA == cntB && arr[j] > arr[j+1]) {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

方法二：标准库排序（推荐）

func sortByBits(arr []int) []int {
    // 使用slices包的SortFunc进行自定义排序
    slices.SortFunc(arr, func(a, b int) int {
        // cmp.Or：先判断第一个表达式，若不为0则返回，否则返回第二个表达式
        return cmp.Or(
            bits.OnesCount(uint(a)) - bits.OnesCount(uint(b)), // 优先按1的个数比较
            a - b // 个数相同时按数值比较
        )
    })
    return arr
}

核心细节

bits.OnesCount()：Go 标准库函数，用于统计无符号整数二进制表示中 1 的个数
排序条件：cntA > cntB || (cntA == cntB && arr[j] > arr[j+1])
- 如果 1 的个数不同，个数多的排后面
- 如果 1 的个数相同，数值大的排后面
cmp.Or()：Go 1.21+ 新增函数，简化多条件比较逻辑