文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡(jiǎn)書(shū)

1. Description

Sort Integers by The Number of 1 Bits

2. Solution

解析：由于最大數(shù)字不超過(guò)10000，因此1的位數(shù)不超過(guò)14位，注意+=的運(yùn)算優(yōu)先級(jí)要低于&，而+的運(yùn)算優(yōu)先級(jí)要高于&。Version 1用右移運(yùn)算獲得1的個(gè)數(shù)，Version 2用的bin函數(shù)，Version 3通過(guò)python自帶的排序函數(shù)進(jìn)行排序。Version 4使用字典保存結(jié)果。

• 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

Reference

1. https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/