数组可以比排序更有效地分组吗? [英] Can an array be grouped more efficiently than sorted?

问题描述

在处理算法问题的示例代码时，我遇到了对输入数组进行排序的情况，尽管我只需要将相同的元素分组在一起，而不必按任何特定的顺序进行分组，例如:

While working on example code for an algorithm question, I came across the situation where I was sorting an input array, even though I only needed to have identical elements grouped together, but not in any particular order, e.g.:

{1,2,4,1,4,3,2}→ {1,1,2,2,4,4,3}或{1,1,2,2,3,4,4}或{3,1,1,2,2,4,4}或.

{1,2,4,1,4,3,2} → {1,1,2,2,4,4,3} or {1,1,2,2,3,4,4} or {3,1,1,2,2,4,4} or ...

这让我感到奇怪:与对数组进行排序相比，是否有可能将数组中的相同元素更有效地组合在一起?

一方面，不需要将元素移动到特定位置这一事实意味着，找到需要更少交换的订单的自由度更高.另一方面，跟踪组中每个元素的位置以及最佳的最终位置是什么，而不是简单地对数组进行排序可能需要更多的计算.

On the one hand, the fact that elements don't need to be moved to a particular location means more freedom to find an order which requires fewer swaps. On the other hand, keeping track of where every element in a group is located, and what the optimal final location is, may need more calculations than simply sorting the array.

逻辑候选将是一种计数排序，但是如果数组长度和/或值范围不切实际地大怎么办?

A logical candidate would be a type of counting sort, but what if the array length and/or value range were impractically large?

为便于讨论，我们假设数组很大(例如一百万个元素)，包含32位整数，每个值中相同元素的数量可以是1到一百万. i>

For the sake of argument, let's say the array is large (e.g. a million elements), contains 32-bit integers, and the number of identical elements per value could be anything from 1 to a million.

更新:对于支持字典的语言，萨尔瓦多·达利(Salvador Dali)的答案显然是正确的方法.我仍然会对听到老式的比较和交换方法，或者如果有的话使用较少空间的方法感兴趣.

UPDATE: For languages with support for dictionaries, Salvador Dali's answer is obviously the way to go. I'd still be interested in hearing about old-fashioned compare-and-swap methods, or methods which use less space, if there are any.

推荐答案

是的，您要做的就是创建一个字典并计算每次有多少个元素.之后，只需遍历该字典中的键，并输出与该键的值相同次数的键即可.

Yes, all you need to do is to create a dictionary and count how many elements of each time you have. After that just iterate over keys in that dictionary and output this key the same number of time as the value of that key.

快速的python实现:

Quick python implementation:

from collections import Counter
arr = [1,2,4,1,4,3,2]
cnt, grouped = Counter(arr), []  # counter create a dictionary which counts the number of each element
for k, v in cnt.iteritems():
    grouped += [k] * v # [k] * v create an array of length v, which has all elements equal to k

print grouped

这将使用潜在的O(n)额外空间对O(n)时间中的所有元素进行分组. (在时间复杂度方面)比在O(n logn)时间内可以实现此目标并且可以就地完成的排序更有效.

This will group all the elements in O(n) time using potentially O(n) additional space. Which is more efficiently (in terms of time complexity) than a sorting which will achieve this in O(n logn) time and can be done inplace.

这篇关于数组可以比排序更有效地分组吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！