根据数字二进制下 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 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
125
粉丝
16
喜欢
92
收藏
46
排名:99
访问:4.7 万
私信
所有博文