有平等的財產分組對象

我有一些任意對象的列表，爲示例的目的假設他們(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)空間）？

來源

2012-06-26 Fanael

有'O（1）'空間的排序算法，排序在這裏很自然。 – unkulunkulu

定義「合理」空間。是O（n）是否合理？ – amit

@amit：是的。編輯了這個問題。 – Fanael

考慮從一個整數數組中除去非唯一條目的問題。這個問題可以通過解決你的問題（線性時間和恆定的空間）來解決，所以你的問題不能簡單地解決。

不幸的是，我找不到一個很好的問題，對這個問題很好的解答，但是這個問題肯定是比較一般和衆所周知的，我相信你會證明這個問題的最佳解決方案。

來源

2012-06-26 08:58:08 unkulunkulu

四年後接受。 – Fanael

最簡單的方法就是使用散列表。這將導致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))

來源

2012-06-26 08:48:58 leppie

值得一提的是：'O（n）'*平均情況*與一個合理的散列函數，這可能是一個合理的假設 – amit

@amit：我可憐誰做了一個糟糕的哈希函數基於一個整數; p – leppie

@leppie：散列函數的好壞並不重要：對於給定數量的桶，存在衝突。問題是輸入是否可以找到它們，而好的散列函數意味着*平均值*隨機輸入不會。 –

有平等的財產分組對象

回答

相關問題