按频率对 Python 列表元素进行排序

您将获得一个包含重复元素的列表。目标是根据元素出现的频率按降序排列这些元素。

例如，假设我们有一个列表 = [2, 2, 2, 2, 3, 1, 1, 1, 4, 4]，其中每个数字代表列表中的一个元素。此列表中元素的出现频率为：2 出现四次，3 出现一次，1 出现三次，4 出现两次。根据频率排序后的列表将是 [2, 2, 2, 2, 1, 1, 1, 4, 4, 3]，其中出现频率最高的元素排在前面。

在 Python 中实现目标有多种方法。下面列出了一些有效且高效的方法

方法 1 - 使用 Python 字典计算每个元素的频率并根据频率计数进行排序。

程序可以总结如下：

• 创建一个字典，将元素存储为键，频率作为值。
• 使用循环遍历列表中的每个元素
• 检查该元素是否已是字典中的一个键。
  • 如果是，则将频率计数加 1
  • 如果不是，则将元素添加为键并将频率设置为 1
• 使用 sorted 函数对字典进行排序。键应为元素的频率，并且 reverse 参数必须为 True。
• Sorted 函数将返回一个元组列表 (键, 频率)。您可以对其进行循环或将其转换为字典。
• 使用必要的方法获取一个包含按频率排序的所有元素的列表。

这是用于按频率对列表元素进行排序的 Python 程序

输出

list_1 = [2, 3, 2, 8, 5, 6, 8, 6, 5, 2, 8]
Sorted list_1 = [2, 2, 2, 8, 8, 8, 5, 5, 6, 6, 3]
list_2 = [1, 4, 1, 4, 5, 4, 3, 3, 5, 2, 1]
Sorted list_2 = [1, 1, 1, 4, 4, 4, 5, 5, 3, 3, 2]

说明

上面的程序创建了一个名为 freq_dict 的字典来存储唯一元素的频率。然后，它使用 for 循环遍历输入列表中的每个元素。然后，它检查该元素是否存在于 freq_dict 中。如果是，则将频率加 1 并继续下一个迭代。否则，创建一个新键并将频率设置为 1。

之后，它使用 sorted 函数对 freq_dict 进行排序，并将频率计数作为键传递。同时，将 reverse 设置为 True，这将按频率降序对字典进行排序。

最后，它创建一个名为 sorted_list 的列表来存储元素。然后，它将迭代字典中每个键的频率次数，并将它们存储在 sorted_list 中。最后，它返回按频率排序的元素列表。

时间复杂度 = O(n logn)： 使用 for 循环遍历列表中的每个元素来计算频率。使用的 sorted 算法的最坏时间复杂度为 O(n logn)。

空间复杂度 = O(n)：我们使用了两个数据结构 sorted_dict 和 sorted_list，它们的大小取决于输入列表的大小。在最坏的情况下，空间复杂度为 O(n)，其中 n 是列表中的元素数量。

方法 2 - 使用 collections 的 Counter 来计算每个元素的频率并根据频率计数进行排序。

我们可以使用 collections 中的 Counter 来减少方法 1 中的代码行数并优化代码。

程序可以总结如下：

• 创建一个 Counter 对象并将输入列表作为参数传递。
• 使用 sorted 函数对输入列表进行排序。将频率作为来自 counter 对象的键传递，并将 reverse 设置为 Ture。
• 返回结果（按频率排序的列表）。

输出

list_1 = [2, 3, 2, 8, 5, 6, 8, 2, 6, 5, 2, 8]
Sorted list_1 = [2, 2, 2, 2, 8, 8, 8, 5, 5, 6, 6, 3]
list_2 = [1, 4, 1, 1, 4, 5, 4, 3, 3, 5, 2, 1]
Sorted list_2 = [1, 1, 1, 1, 4, 4, 4, 5, 5, 3, 3, 2]

说明

上面的程序创建了一个 Counter 对象，将输入列表作为参数传递，并将 Counter 对象（一个字典）存储在 freq_dict 中。

sorted() 函数的 key 参数接受一个 lambda 函数作为输入，其中 lambda 函数接受列表中的一个元素 x 并返回一个元组 (a, b)，其中

• a 是元素 x 的负计数（即 -counter[x]）。通过取计数的负值，我们正在按频率降序对列表进行排序。
• b 是元素 x 本身。包含此项是为了确保在出现平局（即两个元素的频率相同）的情况下，元素按升序排序。

最后，函数返回一个排序后的列表。

时间复杂度 = O(n logn)： sorted 算法的最坏情况时间复杂度为 O(n logn)

空间复杂度 = O(n)：排序列表的大小取决于输入列表的大小。在最坏的情况下，它可以是 O(n)。

方法 3 - 使用 字典推导式 和带 lambda 函数的 sorted() 函数。

程序可以总结如下：

• 使用字典推导式创建一个以元素为键、频率为值的字典。
• 使用 list.count() 来计算每个元素的出现次数。
• 使用 sorted 函数对字典进行排序，并将元素的负频率作为键传递以进行降序排序。
• 如果您想在平局情况下按升序对元素进行排序，可以传递带有频率的值。
• 返回排序后的列表。

输出

list_1 = [2, 3, 2, 8, 5, 6, 8, 2, 6, 5, 2, 8]
Sorted list_1 = [2, 2, 2, 2, 8, 8, 8, 5, 5, 6, 6, 3]
list_2 = [1, 4, 1, 1, 4, 5, 4, 3, 3, 5, 2, 1]       
Sorted list_2 = [1, 1, 1, 1, 4, 4, 4, 3, 3, 5, 5, 2]

说明

在上面的程序中，我们实现了字典推导式的思想来创建一个字典。lst.count(x) 返回该元素在列表中出现的频率，该频率作为 x 的值存储在 freq_dict 中。

然后，我们使用 sorted 函数根据列表中每个元素的频率计数对字典进行排序。在 key 参数中，我们传递了一个 lambda 函数，该函数返回一个元组 (-a, b)，其中 a 是 b 的频率计数，b 是元素本身。通过取频率的负值，我们正在对列表进行降序排序。在出现平局的情况下，元素按升序排序，这就是 b 发挥作用的地方。最后，函数返回一个排序后的列表。

时间复杂度 = O(n logn)： sorted 算法的最坏情况时间复杂度为 O(n logn)

空间复杂度 = O(n)：排序列表的大小取决于输入列表的大小。在最坏的情况下，它可以是 O(n)。