Leetcode 1356. Sort Integers by The Number of 1 Bits

Tyan

发布于 2021-07-08 16:22:35

42300

代码可运行

文章被收录于专栏：SnailTyanSnailTyan

运行总次数：0

代码可运行

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

**解析：**由于最大数字不超过10000，因此1的位数不超过14位，注意+=的运算优先级要低于&，而+的运算优先级要高于&。Version 1用右移运算获得1的个数，Version 2用的bin函数，Version 3通过python自带的排序函数进行排序。Version 4使用字典保存结果。

Version 1

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        result = []
        stat = [[] for i in range(15)]
        for num in arr:
            bits = self.bitCount(num)
            stat[bits].append(num)
        for temp in stat:
            temp.sort()
            result += temp
        return result


    def bitCount(self, num):
        count = 0
        while num:
            count += (num & 1)
            num = num >> 1
        return count

Version 2

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        arr.sort()
        result = []
        stat = [[] for i in range(15)]
        for num in arr:
            bits = bin(num).count('1')
            stat[bits].append(num)
        for temp in stat:
            result += temp
        return result

Version 3

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        return sorted(arr, key=lambda x: [bin(x).count('1'), x])

Version 4

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        arr.sort()
        result = []
        stat = collections.defaultdict(list)
        for num in arr:
            stat[bin(num).count('1')].append(num)
        for index in sorted(list(stat.keys())):
            result += stat[index]
        return result