我有一些任意对象的列表，出于示例的目的，假设它们是 (integer, something-else) 对，但它们基本上可以是任何东西:
[(5, a), (3, c), (2, f), (3, a), (4, c), (1, d), (5, b), (5, d)]
我想根据这些对象的一个属性对这些对象进行分组，以便共享相同属性值的元素在结果列表中相邻。例如，上面的列表按整数值分组:
[(3, a), (3, c), (1, d), (4, c), (2, f), (5, b), (5, a), (5, d)]
如您所见，不需要任何顺序，也不需要稳定的操作。
天真的方法是对列表进行排序。这具有广为人知、经过充分测试和足够快的优点。
不过，我很好奇:是否有一种算法不涉及排序，同时在复杂性方面具有竞争力(O(n) 时间与 O( n) 空间 或 O(n log n) 时间与 O(1) 空间)？
最佳答案
最简单的方法就是使用哈希表。这将导致 O(n) 操作。
伪代码:
foreach (e in list)
hashtable[e.key].append(e.value)
; then 'flatten'
var out = new list
foreach (kv in hashtable)
foreach (v in kv.values)
out.add( new kv(kv.key, v))
关于arrays - 对具有相同属性的对象进行分组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11203633/