1

以下のような配列を取るための最良のアルゴリズムは何ですか？

A {0,1,2,3}

私はそれを以下の配列のように注文することを期待していました：

B {3,1,0,2}

何か案は？

4

7 に答える 7

6

したがって、2つの配列があり、それらが同じデータを異なる順序で保持している場合は、次のようにします。

A = B

それはあなたの状況ではないと思うので、もっと情報が必要だと思います。

于 2008-09-04T17:40:25.380 に答える
3

必要なことは、B の順序を決定し、その順序を A に適用することです。これを達成する 1 つの方法は、B の順序を元に戻し、途中で何が起こるかを追跡することです。次に、Aの逆を行うことができます。

これは大ざっぱなC#です（申し訳ありませんが、実際には実行していません）...

B のコピーを取る:

List<int> B2 = new List<int>(B);

次に、スワップを記録する sort 関数を使用してソートします。

List<KeyValuePair<int,int>> swaps = new List<KeyValuePair<int,int>>();
B2.Sort( delegate( int x, int y ) {
   if( x<y ) return -1;
   if( x==y ) return 0;
   // x and y must be transposed, so assume they will be:
   swaps.Add( new KeyValuePair<int,int>(x,y) );
   return 1;
});

次に、スワップを逆の順序で A に適用します。

swaps.Reverse();
foreach( KeyValuePair<int,int> x in swaps )
{
   int t = A[x.key];
   A[x.key] = A[x.value];
   A[x.value] = t;
}

組み込みの並べ替えアルゴリズムがどのように機能するかによっては、独自のアルゴリズムを展開する必要がある場合があります。マージソートのような非破壊的なものは、正しい結果をもたらすはずです。

于 2008-09-04T17:47:40.557 に答える
2

これが比較子の実装です (LINQ を使用しますが、古い .net バージョンにも簡単に適用できます)。Array.Sort、Enumerable.OrderBy、List.Sort などの並べ替えアルゴリズムに使用できます。

var data = new[] { 1, 2, 3, 4, 5 };
var customOrder = new[] { 2, 1 };
Array.Sort(data, new CustomOrderComparer<int>(customOrder));
foreach (var v in data)
    Console.Write("{0},", v);

結果は2,1,3,4,5,- customOrder にリストされていないアイテムは、指定されたタイプのデフォルトの最後に配置されます (フォールバック コンパレータが指定されていない場合)。

public class CustomOrderComparer<TValue> : IComparer<TValue>
{
    private readonly IComparer<TValue> _fallbackComparer;
    private const int UseDictionaryWhenBigger = 64; // todo - adjust

    private readonly IList<TValue> _customOrder;
    private readonly Dictionary<TValue, uint> _customOrderDict;

    public CustomOrderComparer(IList<TValue> customOrder, IComparer<TValue> fallbackComparer = null)
    {
        if (customOrder == null) throw new ArgumentNullException("customOrder");

        _fallbackComparer = fallbackComparer ?? Comparer<TValue>.Default;

        if (UseDictionaryWhenBigger < customOrder.Count)
        {
            _customOrderDict = new Dictionary<TValue, uint>(customOrder.Count);
            for (int i = 0; i < customOrder.Count; i++)
                _customOrderDict.Add(customOrder[i], (uint) i);
        }
        else
            _customOrder = customOrder;
    }

    #region IComparer<TValue> Members

    public int Compare(TValue x, TValue y)
    {
        uint indX, indY;
        if (_customOrderDict != null)
        {
            if (!_customOrderDict.TryGetValue(x, out indX)) indX = uint.MaxValue;
            if (!_customOrderDict.TryGetValue(y, out indY)) indY = uint.MaxValue;
        }
        else
        {
            // (uint)-1 == uint.MaxValue
            indX = (uint) _customOrder.IndexOf(x);
            indY = (uint) _customOrder.IndexOf(y);
        }

        if (indX == uint.MaxValue && indY == uint.MaxValue)
            return _fallbackComparer.Compare(x, y);

        return indX.CompareTo(indY);
    }

    #endregion
}
于 2010-11-24T17:16:53.003 に答える
1

Dictionary を使用して問題を解決できるので、要素が並べ替え順序に基づいていない関係を持つようにできますか?

于 2009-03-23T16:28:55.893 に答える
1

あなたが与えた例（数値の配列）では、Bを使用するだけなので、Aを並べ替えても意味がありません.

したがって、おそらくこれらは、プロパティの 1 つで並べ替えたいオブジェクトの配列です。

次に、問題のプロパティに基づいて A のアイテムを検索する方法が必要になります (ハッシュテーブルなど)。次に、B (目的のシーケンス) を反復し、A の対応する要素を操作できます。

于 2008-09-04T17:42:36.793 に答える
1

両方の配列には同じ値 (またはほぼ同じ値) が含まれていますが、強制的に同じ順序にする必要があります。たとえば、配列 A では、値「3045」はインデックス位置 4 にあり、配列 B ではインデックス位置 1 にあります。同様の値のインデックス位置が A と同じになるように B を並べ替えたいと思います。

于 2008-09-04T17:42:48.900 に答える
1

それらがほぼ同じである場合、ここにいくつかの擬似コードがあります：

Make an ArrayList
Copy the contents of the smaller array to the arraylist
for each item I in the larger array
    FInd I in the ArrayList
    Append I to a new array
    Remove I from the arraylist
于 2008-09-04T17:47:11.667 に答える