1

長さNのオブジェクトの配列があると仮定します（すべてのオブジェクトは同じフィールドのセットを持っています）。

また、同じ型の値の長さNの配列があります。これは、特定のオブジェクトのフィールドを表します（たとえば、IDを表す数値の配列）。

次に、オブジェクトの配列を、2番目の配列で表されているフィールドで2番目の配列と同じ順序で並べ替えます。

たとえば、次の2つの配列（説明のとおり）と期待される結果は次のとおりです。

A = [ {id: 1, color: "red"}, {id: 2, color: "green"}, {id: 3, color: "blue"} ]
B = [ "green", "blue", "red"]

sortByColorByExample(A, B) == 
    [ {id: 2, color: "green"}, {id: 3, color: "blue"}, {id: 1, color: "red"} ]

'sort-by-example'関数を効果的に実装する方法は？それ以上のことは思いつかないO(N^2)。

4

5 に答える 5

3

Bこれは、要素から要素への全単射があると仮定していますA

の要素からその位置 ( )へのマップ (たとえばM) を作成します。BO(N)

A( )の各要素についてO(N)、マップにアクセスして、並べ替えられた配列内のどこに配置するかを見つけます (O(log(N))マップの効率的な実装を使用)

全体的な複雑さ:O(NlogN)時間とO(N)空間

于 2013-01-11T13:18:55.473 に答える
2

アイテムの色でソートしているとします。次に、各色をその色を持つ A の項目のリストにマップする辞書dを作成します。次に、リスト B の色を反復処理し、色cごとに、リストd [ c ]から値を出力 (および削除) します。これは O( n ) 時間で実行され、O( n )辞書用の余分なスペースが必要です。

B の例に従って A をソートできない場合にどうするかを決定する必要があることに注意してください: エラーを発生させますか? 一致数が最大になる順序を選択しますか? または何？

とにかく、Python での簡単な実装を次に示します。

from collections import defaultdict

def sorted_by_example(A, B, key):
    """Return a list consisting of the elements from the sequence A in the
    order given by the sequence B. The function key takes an element
    of A and returns the value that is used to match elements from B.
    If A cannot be sorted by example, raise IndexError.

    """
    d = defaultdict(list)
    for a in A:
        d[key(a)].append(a)
    return [d[b].pop() for b in B]

>>> A = [{'id': 1, 'color': 'red'}, {'id': 2, 'color': 'green'}, {'id': 3, 'color': 'blue'}]
>>> B = ['green', 'blue', 'red']
>>> from operator import itemgetter
>>> sorted_by_example(A, B, itemgetter('color'))
[{'color': 'green', 'id': 2}, {'color': 'blue', 'id': 3}, {'color': 'red', 'id': 1}]

このアプローチは、シーケンス B に複数の同一の値がある場合を処理することに注意してください。次に例を示します。

>>> A = 'proper copper coffee pot'.split()
>>> B = 'ccpp'
>>> ' '.join(sorted_by_example(A, B, itemgetter(0)))
'coffee copper pot proper'

ここで、 に複数の同一の値がある場合B、対応する要素をA逆の順序で取得しますが、これは単なる実装のアーティファクトです:collections.dequeリストの代わりに (および のpopleft代わりにpop) を使用することで、対応する要素を取得するように調整できます。A元の順序が望ましい場合は、元の順序で。

于 2013-01-11T13:23:01.207 に答える
0
  • 最初の配列を反復処理し、そのようなフィールドとオブジェクトをHashMap比較します。O(n) [これらのキー フィールドの値が重複していると仮定して]List

たとえば。key = green には、フィールド値 Green を持つすべてのオブジェクトが含まれます

  • 次に、2 番目の配列を反復処理し、HashMap からオブジェクトのリストを取得して、別の配列に格納します。O(k) .. (k - フィールドの個別の値)

合計実行時間は O(n) ですが、マップと補助配列に関して追加のメモリが必要です

最後に、要件に従ってソートされた配列を取得します。

于 2013-01-11T13:19:28.017 に答える
0

配列の配列を作成し、サイズ B.length の C と呼びます。A をループします。色が「緑」の場合は、C[0] に入れます。色が「青」の場合は C[1] に、赤の場合は C[2] に入れます。完了したら、C を使用して、元の構造にフラット化します。

于 2013-01-11T13:11:17.440 に答える
0

マージソートに沿ったものの方が良いのではないでしょうか? B 内の要素ごとに 1 つの B.length 配列を作成し、A を通過して適切な小さい配列に配置し、すべてが完了したら配列をマージします。O(2n) 程度である必要があります。

于 2013-01-11T13:17:02.493 に答える