1 题目描述
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
输入：arr = [0,1,2,3,4,5,6,7,8]
输出：[0,1,2,4,8,3,5,6,7]
解释：[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
输出：[1,2,4,8,16,32,64,128,256,512,1024]
解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。
输入：arr = [10000,10000]
输出：[10000,10000]
输入：arr = [2,3,5,7,11,13,17,19]
输出：[2,3,5,17,7,11,13,19]
输入：arr = [10,100,1000,10000]
输出：[10,100,10000,1000]
1 <= arr.length <= 500
0 <= arr[i] <= 10^42 分析问题
问题的本质就是一个排序问题，而不同平常的排序，多了一项条件，就是根据 其二进制表示中1的数目来排序，而数目相同则按数字的大小排序，如果你学过java，到这里 我想你应该知道 如何操作了。Array.sort(arr)
非常清晰的问题：
- 统计序列中每个数的二进制表示中1的个数
- 利用上一步得到的结果数本身进行排序操作
两个步骤中，均有常规版操作以及优化
3 步步解题
- 第一步，统计序列中每个数的二进制表示中1的个数
方法1，求得二进制序列，然后做统计
十进制转二进制
- 最常规的，求模取逆
""" 求一个数的进制 """
def get_num_bin(number):
res_str = ""
while number:
tmp = number % 2
res_str = str(tmp) + res_str
number //= 2
return res_str - 递归求二进制
def get_num_bin(number):
if number < 2:
return number
else:
return get_num_bin(n/2)*10+n%2- 和方法一类似，可以用数组存放、或者累乘法表示成正数，如果有负数要注意变号处理
求得二进制后，我们便可以统计 1的个数。
方法2，巧妙的位运算
另一种方法，不用显示地去求二进制的表示，便可以求其中1的个数，那就这就涉及到了位运算
给定一个数的二进制，我们开始从最右边开始起判断，计数1的个数=> 那么问题来了，如何判断最右边的数是1呢？第二个问题，何时结束呢？
如果能想到0，1这两个特殊的数字以及位运算操作，那么解决办法就来了。
- 1的二进制表示还是1，当用1与一个数做与运算时，得到的结果如果是1，那么最右边就是1，得到结果为0，那么就不是1。
- 何时结束，当然是遍历到最左边了，但是我们没必要知道二进制序列多长，况且我们还是从后面往前面走，如果去循环遍历判断计算1的个数，那和前面的方法没有什么区别了。另一种
while式的思考方法当然是序列中没有1了，那我们就没有必要继续判断了。那么问题来了，如何判断序列中没有1了呢？ 那么解决办法来了=> 0的二进制还是0，是唯一一个二进制表示没有1的数。假如我们有一种方法，使得这个数不断地向0靠近，并且保证最右边一位被更新。那么这种方法就是 右移
根据前面的分析，写处代码如下：
def get_a_number_bin_count(number):
"""
得到一个数的二进制表示形式中 1 的个数
:param number:
:return:
"""
res_count = 0
while number:
if number & 1:
res_count += 1
number = number >>1
return res_count但是上面的代码对于负数就不那么通用了，虽然此题的所有测试样例都是正数，但是有必要学习更加适用的方法。
我们先来观察一个整数与它的次小整数 在二进制表示上的区别，二进制的含义是什么=> 满二进1。一个数加1，会发生的情况：最右边加1，满2进1，该位变0。进为后下一位为2那么继续进位，该位变0，如果进位后位1，那么就停止。我们可以发现的是，一个数加1后，在位表示上的变化是 遇到一个白马王子->1停止，而这个白马王子是最次等的，是这个数加1后最右边的那个1，或许再往左还有更好的，但是它满足了，停止脚步了.
从上面的分析中，我们可以得出一个结论：一个整数与它的次小整数在二进制表示上的差异是: 将该数右边的1变为0，最右边那个1的右边的所有位变为1。以1100得到1011为例
有了上面的结论，我们去做个小实验： 用一个整数和它的次小整数做 与 运算，发现操作结果恰恰是将这个整数最右边的1变为了0
1100 & 1011 = 1000
根据前面的分析，我们可以写处这样的代码
def get_a_number_bin_count(number):
"""
得到一个数的二进制表示形式中 1 的个数
:param number:
:return:
"""
res_count = 0
while number:
number = number & (number - 1)
res_count += 1
return res_count- 利用上一步得到的结果与数本身进行排序操作,
最简单的冒泡排序
def sort_by_bits(self, array):
"""
根据数字的二进制形式中的1的个数 对 array 进行排序
:param array:
:return: a array,排好序的结果
"""
def get_a_number_bin_count(number):
"""
得到一个数的二进制表示形式中 1 的个数
:param number:
:return:
"""
res_count = 0
while number:
number = number & (number - 1)
res_count += 1
return res_count
tmp_list = [(i, get_a_number_bin_count(i)) for i in array]
print(tmp_list)
""" 排序 """
for i in range(len(tmp_list)):
for j in range(len(tmp_list)):
if tmp_list[i][1] < tmp_list[j][1]:
tmp_list[i],tmp_list[j] = tmp_list[j],tmp_list[i]
else:
if tmp_list[i][0] < tmp_list[j][0]:
tmp_list[i],tmp_list[j] = tmp_list[j],tmp_list[i]
return [i[0] for i in tmp_list]利用现成的:
return sorted(arr, key=lambda x: (get_a_number_bin_count(x), x), reverse=False)当然，如果你对python的常用函数熟悉，你还可以写处更简短的代码：
return sorted(arr, key=lambda x: (bin(x).count("1"), x), reverse=False)4 总结
- 一个整数的二进制上最右边的1变为0，最右边那个1的右边的所有位变为1，便得到次小整数
- 0是唯一一个二进制表示没有1的数
- 一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1。
