4

いくつかの任意のオブジェクトのリストがあります。例では、それらが(integer, something-else)ペアであると想定していますが、基本的には何でもかまいません。

[(5, a), (3, c), (2, f), (3, a), (4, c), (1, d), (5, b), (5, d)]

これらのオブジェクトをプロパティの1つに基づいてグループ化し、そのプロパティの同じ値を共有する要素が結果のリストで隣接するようにします。たとえば、上記のリストは整数値でグループ化されています。

[(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)

4

2 に答える 2

2

最も簡単な方法は、ハッシュテーブルを使用することです。これにより、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-26T08:48:58.223 に答える
1

整数配列から一意でないエントリを削除する問題を考えてみましょう。この問題は、(線形時間と定数空間で) 問題を解決することによって解決できるため、それよりも簡単に問題を解決することはできません。

残念ながら、この問題に対する適切な回答を含む適切な質問を見つけることができませんが、これは間違いなくより一般的でよく知られています。そのための最良の解決策を証明してくれると確信しています。

于 2012-06-26T08:58:08.130 に答える