1

全て、

このアルゴリズムを（仕事のために）できるだけ早くきれいに実装するための賢い方法が必要です。言語固有の問題をすべて取り除き、これに要約したと思います。

A と B の 2 つの配列があります。

A には名前のリストがあります {Apple、Apple、Banana、Banana、Banana、Carrot、...} 各 i 番目の値には、A に出現できる回数の上限はありません。 「アップル」または無数。

A の各エントリには、B に一致するエントリがあります (多対多のマッピング)。例えば：

A[0] = "Apple"      B[0] = "0027"
A[1] = "Apple"      B[1] = "0028"
A[2] = "Banana"     B[2] = "0073"
A[3] = "Banana"     B[3] = "0041"
A[4] = "Banana"     B[4] = "0069"

A のエントリのインスタンスが 100 以下の場合 (バナナが 100 以下の場合)、それらはすべて同じ初期 "B" 値を共有する必要があります。100 を超える場合、最初の 100 は同じ B 値を共有する必要がありますが、次の 100 は B[i + 100] 番目の値を持ちます。

りんごが102個ある場合の例

A[0]   = "Apple"       B[0]   = "0027"
A[1]   = "Apple"       B[1]   = "0028"
...
A[99]  = "Apple"       B[99]  = "0073"
A[100] = "Apple"       B[100] = "0041"
A[101] = "Apple"       B[101] = "0069"
A[102] = "Banana"      B[102] = "0123"

次に、私が望む結果は次のとおりです。

A[0]   = "Apple"       B[0]   = "0027"
A[1]   = "Apple"       B[1]   = "0027"
...
A[99]  = "Apple"       B[99]  = "0027"
A[100] = "Apple"       B[100] = "0041"
A[101] = "Apple"       B[101] = "0041"
A[102] = "Banana"      B[102] = "0123"

私が考案したくだらないアルゴリズムを思いつくことができるスーパーブレインがそこにいると確信しているので、それを見てみましょう!

編集1：これは仕事のためだったと指摘する必要があると思います。これは、誰かが見て、私が思いついたものよりも優れた解決策を考え出したいと思うかもしれない楽しい挑戦だと思いました.

編集 2:私のばかげた間違いを指摘してくれたダニエルに感謝します。

比較のためだけの私のソリューション（疑似コード）：

最初に d と呼ばれる B のハッシュ/辞書を作成します。ここで、d[ "Apple" ] = A 内の Apple のインスタンスの数です。

while (i < A.count)
{
    string cmp = A[i];
    int v = d[cmp];
    int j=i;

    while (v--) {
       B[j++] = B[i];

       if (j %100 == 0)
       i += j
    }
    i+= d[cmp];
}

メモリからこれを行うと、インデックスを台無しにしないことを願っています...

4

4 に答える 4

2

質問を理解し、配列がソートされていると仮定する限り、C＃での私の提案。

String[] A = GetAs();
String[] B = GetBs();

Int32 count = 0;
Int32 index = 1;

while (index < A.Length)
{
   if (A[index] != A[index - 1])
   {
      count = 0;
   }

   currentCount++;

   if ((A[index] == A[index - 1]) && (count % 100 != 1))
   {
      B[index] = B[index - 1];
   }

   index++;
}

それが好きなら、コンパクト（そしてゼロベースのカウント）です。

String[] A = GetAs();
String[] B = GetBs();

Int32 c = 0, i = 1;

while (i < A.Length)
{
   c = (A[i] == A[i - 1]) ? c + 1 : 0;

   B[i] = ((A[i] == A[i - 1]) && (c % 100 != 0)) ? B[i - 1] : B[i];

   i++;
}
于 2009-09-04T13:00:02.230 に答える
0

次のような辞書/ハッシュテーブルを作成したいと思います

{'Apple':
    {'NumberSeen':102,
     'BValues':['0027','0041']
    },
 'Banana':
    {'NumberSeen':1,
     'BValues':['0123']
    }
}

次にこれをループし、NumberSeen%100 = 1 の場合に新しい b 値を追加してから、このディクショナリから B 配列を再作成します。

編集:これにより、ソートされていないリストを処理する読み取り可能なソリューションが得られます。「リストはソートされています」というコメントを見たところです。これは、O(1) スペースでより簡単に実行できることを意味しますが、コードがどれほど明確になるかはわかりません。

于 2009-09-04T12:59:47.503 に答える
0

私は Daniel Brückner のソリューションが本当に気に入っていますが、それを 1 つ強化できると思います。「A」がソートされており、100 個の連続した同一の果物の噴出が一般的であると仮定すると、次のチェックを追加することでそれを利用できます。

String[] A = GetAs();
String[] B = GetBs();
Int32 c = 0, i = 1;
while (i < A.Length)
{   
    if(i+99 < A.Length && A[i] == A[i+99])
    {
        for(int j=1;j<100;j++) b[i+j] = b[i];

        i = i+99;
    }
    else
    {
        B[i] = (A[i] == A[i - 1]) ? B[i - 1] : B[i];   
        i++;
    }
}
于 2009-09-04T14:31:24.197 に答える
0 
String curFruit = A[0];
int curFruitCount = 0;
for (int i = 1; i < A.length; i++) {
    if (A[i].equals(curFruit) && curFruitCount < 100) {
        B[i] = B[i-1];
        curFruitCount++;
    }else{
        curFruit = A[i];
        curFruitCount = 1;
    }
}
于 2009-09-04T13:05:18.653 に答える