文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Sort Integers by The Number of 1 Bits
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
