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

题面

将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
返回排序后的数组。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/sort-inte...

思路分析

二制数1计数，后排序

哈希+排序

• 哈希二进制1出现次数分组
• 哈希值排序，构建哈希键切片并排序
• 依键还建

import "sort"
import "strconv"
import "strings"

func sortByBits(arr []int) []int {
    m := make(map[int][]int, 0)
    for _, v:= range arr {
        cnt := strings.Count(strconv.FormatInt(int64(v),2),"1")
        if _, ok := m[cnt];ok {
            m[cnt]=append(m[cnt], v)
        }else{
            m[cnt]=[]int{v}
        }
    }
    keys := []int{}
    for cnt, grp := range m {
        sort.Ints(grp)
        m[cnt]=grp
        keys = append(keys, cnt)
    }
    sort.Ints(keys)
    rs := []int{}
    for _, k := range keys {
        rs = append(rs, m[k]...)
    }
    return rs
}

自定义计数与排序

计数与排序函数

• 右移循环计数，求模得二进制1的个数
• 用golang库函数sort.Slice 确定排序规则
• sort.Slice 自定义匿名函数入参为切片索引，而非元素值
• 或运算模拟条件if--else隐性优先级规则,且运算短路实现多条件断言

import "sort"

func sortByBits(arr []int) []int {
    var Count func(int) int
    Count = func(c int)(cnt int){
        for ;c > 0;c >>=1 {
             cnt += c %2
        }
        return cnt
    }   
    sort.Slice(arr, func(i,j int)bool {
        ic, jc := Count(arr[i]),Count(arr[j])
        return ic < jc || ic == jc && arr[i]< arr[j]
    })
    return arr
}

本作品采用《CC 协议》，转载必须注明作者和本文链接