0

例えば...

  1. 1から1000までのランダムな値で初期化される整数の配列があります
  2. 配列には1Mの要素があります（おそらくもっと多くの要素がありますが、これは単なる例です）
  3. 各要素の出現回数は10から1010の間でなければなりません

上記の基準を満たすようにこの配列の要素を調整する最も速い方法は何ですか？

発生の最大数がarray.Length（1M）/ valuesSpan（1000）に近い場合、私の最初の解決策は単純に遅すぎます

私は次のようなことを試みました（これは発生の最大数を調整するためだけのものであり、下限の解決策はほとんど同じです）：

Int64[] DistinctArrayElements = distinctArrayElements;
Dictionary<Int64, Int32> occurrences = new Dictionary<Int64, Int32>();

foreach (Int64 DistinctElement in DistinctArrayElements)
{
    occurrences.Add(DistinctElement, 0);
}

foreach (Int64 ArrayElement in Arr)
{
    occurrences[ArrayElement] += 1;
}
//I know this initialization can be done more nicely, so don't bother with this.

for (int j = 0; j < Arr.Length; j++)
{
    if (occurrences[Arr[j]] > upperNoOfOccurrences)
    {
        for (int i = 0; i < Arr.Length; i++)        
        {
            if (occurrences[Arr[i]] < upperNoOfOccurrences)
            {
                Arr[j] = Arr[i];
                occurrences[Arr[i]] += 1;
                occurrences[Arr[j]] -= 1;
            }
        }
    }
}
4

3 に答える 3

0

表示が少ない数字が最初になるように辞書を並べ替えます。このように、適切な数を毎回探す必要はなく、発生数の少ない数に置き換えるだけです。これを説明するための擬似コードは次のとおりです。

struct dict {
    key, value
}

linkedList<dict> occurrences;

initialize occurrences
sort it (smallest values first)

// start from the one with greatest number of occurrences
n = occurrences.last;

// keep going until occurrences of n is greater than upperNoOfOccurrences
while n.value.value > upperNoOfOccurrences and didn't reach first element
    repeat = true

    do:
        // required occurrences to subtract to be within the limit
        required = upperNoOfOccurrences - n.value.value

        // maximum occurrences we can add to the first
        maxAllowed = upperNoOfOccurrences - occurrences.first.value.value

        // if we can do that
        if required < maxAllowed:
            occurrences.first.value.value += required
            n.value.value -= required
            repeat = false
        else:    // n.value.value is still greater than upperNoOfOccurrences
            occurrences.first.value.value += maxAllowed 
            n.value.value -= maxAllowed 
            repeat = true
        end if

        // keep occurrences sorted
        newPos = occurrences.first.next
        while occurrences.first.value > newPos.value.value:
            newPos = newPos.next

        move occurrences.first before newPos
    while repeat
end while

now rebuild your array with occurrences. it will
be sorted  but it doesn't matter does it? ;)
于 2011-10-25T16:07:32.083 に答える
0

これは、基準を満たす一連の数値を均一にサンプリングする単純で正確な方法です。

  1. M = 個別の値の数とします。N = 配列要素の数。L = 各値のインスタンス数の下限。U = カウントの上限。D=UL。たとえば、M=1000、N=1000000、L=10、U=1010、D=1000 です。
  2. サイズ M*D の配列 S を作成します。S の最初の N 個のエントリを 1 に設定し、残りを 0 に設定します。
  3. Fisher-Yates シャッフルを介して S をシャッフルします。（リンクはこちら）
  4. サイズ M の配列 T を作成します。
  5. M まで、iT[i] = L + S[i D] + S[i D+1] + ... + S[i*D+D-1] を設定します。
  6. サイズ N の配列 V を作成します。0i番目の値のT[0] インスタンスで埋めますi。S には N 個の 1 が含まれているため、V は完全かつ正確に満たされます。
  7. Fisher-Yates シャッフルを介して V をシャッフルします。次に、配列 V は元の基準を満たします。

手順 2 ～ 5 は O(M D) であり、6 ～ 7 は O(N+M) であることに注意してください。あなたの問題文。

于 2011-10-25T21:29:30.643 に答える
0

あなたがやりたいことの本当の意味を理解することはできません。しかし、これだけ配列を処理するのはもったいないようです。ループを 1 回実行するだけですべてを実行できます (「空き」の一意の値がなくなった場合は、前方へのちょっとした覗き見が必要です)。以下は確かに私が書いたコードの中で最も優れたものではありませんが、問題の解決策になると思います。

HashSet<long> forbidden = new HashSet<long>(); // maximum size of 1000, contains values that exceeded the limit
Queue<long> remaining = new Queue<long>(1000); // stores found unique values within the limit in a queue, that will be used if we bounce into the limit
Dictionary<long, int> frequencies = new Dictionary<long, int>(1000);
int lastPeekIndex = 0;
for (int i = 0; i < Arr.Length; i++) {
  if (!frequencies.ContainsKey(Arr[i])) {
    frequencies[Arr[i]] = 0;
    remaining.Add(Arr[i]);
  }

  if (frequencies[Arr[i]] == upperLimit) {
    if (!forbidden.Contains(Arr[i])) forbidden.Add(Arr[i]);
    var next = Int64.MinValue;
    try {
      next = remaining.Dequeue();
      while (forbidden.Contains(next)) next = remaining.Dequeue();
    } catch (InvalidOperationException) { // Arrr! we have not yet observed enough unique values
      for (int j = Math.Max(i, lastPeekIndex) + 1; j < Arr.Length; j++)
        if (!frequencies.ContainsKey(Arr[j])) {
          frequencies[Arr[j]] = 0;
          next = Arr[j];
          lastPeekIndex = j;
        }
    }
    Arr[i] = next;
    frequencies[next]++;
    if (frequencies[next] < upperLimit) remaining.Enqueue(next);
  } else frequencies[Arr[i]]++;
}

これもチェックしなかったので、これは下限をチェックしないことに注意してください。2 番目のパスではあまり発生しない値に注意する必要があると思います。最初のパスの後にそれらを別のキューに入れ、キューが空になるまで配列を何度も繰り返すことができます (おそらく、2 番目のパスで必要な完全な反復は 1 回未満です)。

于 2011-10-25T15:26:54.647 に答える