Java 中按集合位计数排序数组

给定一个包含自然数的数组。我们的任务是根据数组中元素的二进制表示中的集合位数对输入数组进行排序。也就是说，集合位数较多的数字应排在集合位数较少的数字之后。如果两个数字具有相同的集合位数，则它们应按照它们在输入数组中出现的顺序显示。假设输入数组中的任何数字都能容纳在 32 位整数中。

示例 1

输入

int arr[] = {1, 4, 2, 8, 16, 64, 32, 128}

输出 {1, 4, 2, 8, 16, 64, 32, 128}

说明：首先，让我们看一下输入数组中每个数字的二进制表示。

1 -> 1, 4 -> 100, 2 -> 10, 8 -> 1000, 16 -> 10000, 64 -> 1000000, 32 -> 100000

128 -> 10000000

我们看到，在它们的二进制表示中，每个数字只包含一个集合位。因此，输出的元素顺序与它们在输入数组中出现的顺序相同。

示例 2

输入

int arr[] = {11, 24, 7, 28, 128, 60, 132, 16, 5}

输出 {128, 16, 24, 132, 5, 11, 7, 28, 60}

说明：首先，让我们看一下输入数组中每个数字的二进制表示。

11 -> 1011, 24 -> 11000, 7 -> 111, 28 -> 11100, 128 -> 10000000, 60 -> 111100, 132 -> 10000100, 16 -> 10000, 5 -> 1001

11 有 3 个集合位。24 有 2 个集合位。7 有 3 个集合位。类似地，我们可以计算其他数字的集合位数。我们看到数字 16 和 128 只有一个集合位，并且 128 出现在 16 之前。因此，输出中的前两个元素是 128 和 16。24、132 和 5 有 2 个集合位。因此，它们是输出中的下一个元素。之后是 11、7 和 28，因为它们有 3 个集合位。最后，是数字 60。

我们看到，在它们的二进制表示中，每个数字只包含一个集合位。因此，输出的元素顺序与它们在输入数组中出现的顺序相同。

方法：使用 Map

使用 Map，我们可以实现所需的结果。我们将不得不存储一个哈希映射，其键是数字中的集合位数，值是存储数字的向量或数组列表。因此，对于输入数组 {1, 2, 3, 4, 5}，哈希映射将如下所示。

[1] -> {1, 2, 4} and [2] -> {3, 5}，其中方括号中的值是键，其对应的列表是值。之后，我们可以使用循环（从 0 到 32），以便轻松显示输出。观察以下程序以获得更好的理解。

文件名：SetBitCntSort.java

输出

For the input array: 
1 4 2 8 16 64 32 128 
The sorted arrange as per the set bits are: 
1 4 2 8 16 64 32 128 

For the input array: 
11 24 7 28 128 60 132 16 5 
The sorted arrange as per the set bits are: 
128 16 24 132 5 11 7 28 60

复杂度分析：addAll() 方法需要 O(n) 时间，并且该方法被调用 n 次。因此，程序的总时间复杂度为 O(n2)。该程序还使用辅助空间，使得程序的空间复杂度为 O(n)，其中 n 是输入数组中元素的总数。

我们可以在时间和空间复杂度方面进行一些优化。以下方法说明了这一点。

方法：使用自定义比较器

通过在调用内置排序方法时使用自定义比较器（比较器方法是负责根据排序方法进行排序的方法），我们可以减少程序的空间复杂度。以下是比较器方法的伪代码

Comparator(int n1, int n2)

If (cntSetBits(n1) > cntSetBits(n2))

return false;

else

return true;

该方法对数字中的集合位数进行比较，如果第二个数字的集合位数较少，则返回 false；否则，由于排序顺序是升序，因此返回 true。请看以下程序。

文件名：SetBitCntSort1.java

输出

For the input array: 
1 4 2 8 16 64 32 128 
The sorted arrange as per the set bits are: 
1 4 2 8 16 64 32 128 

For the input array: 
11 24 7 28 128 60 132 16 5 
The sorted arrange as per the set bits are: 
128 16 24 132 5 11 7 28 60

复杂度分析：由于程序使用了排序技术，因此程序的时间复杂度为 O(n x log(n))。由于程序没有使用任何数据结构来存储任何值，因此空间复杂度为 O(1)。

让我们进行一些进一步的优化以降低时间复杂度。

方法：计数排序

使用计数排序，也可以根据集合位数对元素进行排序。

算法

步骤 1：创建一个大小为 33 的二维数组列表。我们取大小 33 是因为每个整数都可以容纳在 32 位整数中。索引为零的列表显示具有零集合位的元素。索引为 1^st 的列表显示只有一个集合位的元素，依此类推。

步骤 2：现在，开始遍历数组的所有元素，并计算每个元素的集合位数。设集合位数为“cnt”，然后应将该元素推送到数组索引为“cnt”的列表中。

步骤 3：清空输入列表以存储答案。这是为了避免浪费空间。

步骤 4：现在，将输入列表显示在控制台上，并将答案存储在其中，使得集合位数较少的数字出现在集合位数较多的数字之前。

让我们看一下上述步骤的实现。

文件名：SetBitCntSort2.java

输出

For the input array: 
1 4 2 8 16 64 32 128 
The sorted arrange as per the set bits are: 
1 4 2 8 16 64 32 128 

For the input array: 
11 24 7 28 128 60 132 16 5 
The sorted arrange as per the set bits are: 
128 16 24 132 5 11 7 28 60

复杂度分析：由于程序使用线性循环来完成任务，因此程序的时间复杂度为 O(n)。该程序还使用数组列表来存储数字，因此程序的空间复杂度为 O(n)，其中 n 是输入数组中元素的总数。