- 610 名前：デフォルトの名無しさん mailto:sage [2013/02/02(土) 20:56:41.94 ]
- リスト内の要素をグループ化するアルゴリズムを考えてるんだけど、
単純にソートアルゴリズムを使うよりも少ない計算量でできる？
[入力] 少なくとも大小の比較ができる要素がランダムに並んだリスト
[出力] 同値な要素が必ず隣同士にあるリスト（入力と同じ要素数で、同じ要素を持つ）
出力のリストは上記の条件に合えば、どのような要素の並びでも構わない。
<例>
入力 = [3, 5, 2, 3, 5, 2, 5, 2, 1, 5]
出力例1 = [3, 3, 5, 5, 5, 5, 2, 2, 2, 1]
出力例2 = [5, 5, 5, 5, 1, 3, 3, 2, 2, 2]
もちろんソートアルゴリズムを使えば O(n log n) でできるんだけど、
ソートより条件が緩いから、もっと早くできるかな、と。
