如何根据设置的位对数组进行排序

Question

按设置的位数对数组进行排序。例如，

• 输入：arr = [0,1,2,3,4,5,6,7,8]
• 输出：[0,1,2,4,8,3,5,6,7]

示例2

• 输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
• 输出：[1,2,4,8,16,32,64,128,256,512,1024]

我尝试计算一个数字中设置的位数，之后我陷入困境。我是完全的初学者。

arr = [1,2,3,4,5,6]
for i in range(len(arr)):
    a = arr[i]
    count1 = 0
    while(a>0):
        d = int(a/2)
        s =  a%2
        a = d
        #print(s, end=" ")
        if s == 1:
            count1+=1
    print(arr[i],count1)

Answer 1

如果您的所有给定值都是

int

类型，那么这里有两个版本可以使用，如您的示例所示：

Python 3.10 或更高版本

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]
sorted_arr = sorted(arr, key=int.bit_count)
print(sorted_arr)

使用

key

参数，我们指定如何定义自定义排序顺序：给定的函数将应用于数组中的每个元素，并且数组元素将根据各自的结果进行排序。在我们的例子中，我们可以直接使用

int.bit_count()

，因为它计算整数的设置位。

早期的 Python 版本

对于 3.10 之前的 Python 版本，尚未引入

int.bit_count()

，我们可以等效使用，如

int's

文档所建议：

sorted_arr = sorted(arr, key=lambda i: bin(i).count("1"))

在这种情况下，我们无法直接将现有方法或函数传递给

key

参数，因此我们使用 lambda 函数即时创建自己的方法或函数。

Answer 2

要按每个元素中设置的位数对数组进行排序，您可以使用

sorted

函数和自定义键函数来计算每个元素中设置的位数。

arr = [0,1,2,3,4,5,6,7,8]

def count_set_bits(num):
    count = 0
    while(num > 0):
        if num % 2 == 1:
            count += 1
        num = num // 2
    return count

sorted_arr = sorted(arr, key=count_set_bits)
print(sorted_arr)

Answer 3

#include bool cmp(int a, int b){return __builtin_popcount(a) > __builtin_popcount(b);}void sortSetBitsCount(std::vector &arr, int size){ std::stable_sort(arr.begin(), arr.end(), cmp);}int main(){int n;std::cin >> n;std::向量 arr(n);for (int i = 0; i < n; ++i){std::cin >> arr[i]; }sortSetBitsCount(arr, n);for (int i = 0; i < n; ++i){std::cout << arr[i] << ' ';}return 0;}