3

1000 個の大きな数値 (64 ビットの数値も可能) を持つ配列 (1000 要素スペースを超える) があります。配列内の数値は、必ずしもソートされているとは限りません。
前の 1000 とは異なる 1001 番目の位置に一意の番号を生成する必要が
あります。使用したアプローチが最適であることを正当化します。

私の答え (これがどの程度正しかったかはわかりません): 数字を並べ替え、0 の位置から始めます。1000位の数字＋1が必要枚数です。

これに対するより良い提案はありますか？

4

5 に答える 5

4

1001要素の補助配列を作成します。これらすべてを1（またはtrueまたはYまたは選択したもの）に設定します。メイン配列を実行します。1..1000の範囲の数値が見つかった場合は、補助配列の対応する要素を0アウト（または他の方法で改ざん）します。最後に、0（またはfalse）ではない補助配列の最初の要素は、主配列にない数値に対応します。

これは単純で、時間計算量のO（n）です。ここで、nはメイン配列の要素の数です。

于 2012-06-06T13:31:05.453 に答える
0 
unsigned ii,slot;

unsigned array [ NNN ];
/* allocate a histogram */
#define XXX (NNN+1);
unsigned histogram [XXX];
memset(histogram, 0, sizeof histogram);

for (ii=0; ii < NNN; ii++) {
        slot = array [ii ] % XXX;
        histogram[slot] += 1;
        }
for (slot=0; slot < NNN; slot++) {
        if ( !histogram[slot]) break;
        }

/* Now, slot + k * XXX will be a 
** number that does not occur in the original array */

注: これはハイ パフォーマンス マークに似ていますが、少なくとも私はコードを入力しました...

于 2012-06-06T13:38:25.193 に答える
0

不器用な C# 実装の試み

public class Test
{
    public List<int> Sequence { get; set; }

    public void GenerateFirstSequence()
    {
        Sequence = new List<int>();
        for (var i = 0; i < 1000; i++)
        {
            var x = new Random().Next(0, int.MaxValue);
            while (Sequence.Contains(x))
            {
                x = new Random().Next(0, int.MaxValue);
            }
            Sequence.Add(x);
        }
    }

    public int GetNumberNotInSequence()
    {
        var number = Sequence.OrderBy(x => x).Max();
        var mustRedefine = number == int.MaxValue && Sequence.Contains(number);
        if (mustRedefine)
        {
            while (Sequence.Contains(number))
            {
                number = number - 1;
                if (!Sequence.Contains(number))
                    return number;
            }
        }
        return number + 1;
    }
}
于 2012-06-06T14:08:41.607 に答える
0

私はこの問題についていくつかの考えを持っています:

1000 個の要素を含むハッシュ テーブル H を作成できます。配列の名前が A で、要素ごとに 1000 のリマインダーがあるとします: m[i] = A[i] % 1000.

A[i] と A[j] の間に矛盾がある場合、A[i] % 1000 = A[j] % 1000 となります。つまり、インデックス k が存在しなければならず、1000 による要素のリマインダはありません。 k にすると、k は取得する数値です。

競合がまったくない場合は、結果として H[1] + 1000 を選択してください。

このアルゴリズムの複雑さは O(l) です。ここで、l は元のリスト サイズを示します。この例では、l = 1000 です。

于 2012-06-06T14:37:30.790 に答える
0

配列を並べ替える場合、一意の番号には次の 3 つの可能性があります。

  1. array[999]+1、array[999] が INT_MAX と等しくない場合
  2. array[0]-1、array[0] が INT_MIN と等しくない場合
  3. array[i+1]-array[i]>1 (0<=i<=998) の場合、array[i] と array[i+1] の間の数値。前の 2 回の試行が失敗した場合、配列内の 2 つの要素の間に数値があることが保証されることに注意してください。

このソリューションは、1002 番目、1003 番目などでも機能することに注意してください。

于 2012-06-06T13:55:28.260 に答える