-1

2つの配列があります

Array1 {5,6,7,8}

と

Array2 {2,1,1,0}

ある条件を満たすパターンはこちら

8,6,5,7

条件: Array2 のそれぞれの要素から Array1 の 8 までのパターンを考慮すると、パターンの左側に 8 より大きい 0 の要素があることを示しています。などなど……。

2 つの配列が与えられた場合、パターンを生成する方法があります。任意のアルゴリズム ロジックがあれば幸いです。

4

2 に答える 2

3

動作するはずのアルゴリズムは次のとおりです。

  • 数字を並べ替えます。（編集：番号で、次に左カウントで）
  • 数字ごとnに、左に大きな数字が必要なため、左n+1から 3 番目の空きスロットに配置します。
  • それほど多くの空きスロットが残っていない場合、元の 2 つの配列ではそのようなパターンは存在できません。

これがあなたの例でどのように機能するかです：

  • 最小の数字である 5 から始めます。左側に 2 つの大きなアイテムが必要です。他は大きいので左から3番目に。_ _ 5 _
  • 次に小さいのは 6 です。左側に 1 つ大きいアイテムが必要です。残りのアイテムはすべて大きいので、2 番目の空きスロットに入れる必要があります。_ 6 5 _
  • 次に小さいのは 7 です。左側に 1 つ大きいアイテムが必要です。残りのアイテムはすべて大きいので、2 番目の空きスロットに入れる必要があります。_ 6 5 7
  • 次は 8 です。左側に大きなアイテムは必要ありません。最初の空きスロットに入れる必要があります。8 6 5 7

C# での大まかな実装を次に示します。

public static int[] algorithm(int[] numbers, int[] counts)
{
    var pairs = numbers                         // EDIT:
        .Zip(counts, (n, c) => new { n, c })    // This is needed to
        .OrderBy(p => p.n)                      // correctly handle
        .ThenBy(p => p.c)                       // duplicate numbers
        .ToArray();
    int[] output = new int[pairs.Length];
    List<int> freeIndices = Enumerable.Range(0, pairs.Length).ToList();
    for (int i = 0; i < pairs.Length; i++)
    {
        if (pairs[i].c < freeIndices.Count)
        {
            int outputIndex = freeIndices[pairs[i].c];
            freeIndices.RemoveAt(pairs[i].c);
            output[outputIndex] = pairs[i].n;
        }
        else
        {
            throw new ArgumentException();
        }
    }
    return output;
}

編集:元のコードは重複した番号を正しく処理しませんでした。このバージョンではそうする必要があります。

于 2012-11-20T14:45:06.207 に答える
1

これを 2 つの配列と考えるのではなく、Number/LeftCount ペアの 1 つのリストと考えたいと思います。

最初に (LeftCount == 0) のペアのセットのみを考えます。このセットのうち、番号が最も小さいもの ( n) を選択します。

画面に書き込みnます。

このペアをリストから削除します。

Number より小さい残りのすべてのペアについてn、LeftCount をデクリメントします。

リストに残っているペアがなくなるまで繰り返します。

 

このアルゴリズムの考え方を理解していれば、それを 2 つの別個の配列としてコーディングすることはそれほど難しくありません。

于 2012-11-20T15:01:46.713 に答える