0

最初のカバー プレフィックスについて、C++ でちょっとした互換性テストを行いました。ここで定義されているように、

N 個の整数で構成される空でないゼロ インデックスの配列 A が与えられます。配列 A の最初のカバー プレフィックスは、最小の整数 P で0 ≤ P < Nあり、配列 A に出現するすべての値が連続して出現するようなものA[0], A[1], ..., A[P]です。

たとえば、次の 5 要素配列 A の最初のカバー プレフィックスは次のとおりです。

A[0] = 2
A[1] = 2
A[2] = 1
A[3] = 0
A[4] = 1

配列 A にあるすべての値が含まれている[ A[0], A[1], A[2], A[3] ]ため、 は 3 です。[2, 2, 1, 0]

関数を書く

class Solution { public int ps(int[] A); }

これは、N 個の整数で構成されるゼロ インデックスの空でない配列 A を指定すると、A の最初のカバー プレフィックスを返します。

と仮定する：

  • N は [1..1,000,000] の範囲内の整数です。
  • 配列 A の各要素は [0..N−1] の範囲内の整数です。

たとえば、次のような配列 A があるとします。

A[0] = 2
A[1] = 2
A[2] = 1
A[3] = 0
A[4] = 1

上記で説明したように、関数は 3 を返す必要があります。

複雑：

  • 予想される最悪の場合の時間計算量は O(N) です。
  • 予想される最悪の場合のスペースの複雑さは O(N) であり、入力ストレージを超えています (入力引数に必要なストレージは数えません)。

私の解決策は次のとおりです (最適とは言っていません)...しかし、スコアは 48/100 しかありませんでした...間違った答えを引き起こしているコードの問題を確認できる人がいるかどうか疑問に思っていますか? ありがとう

int ps ( int A[], int N )
{

long unique_array [N-1];
memset( unique_array, -1, N - 1 );
long value = 0, counter = 0, unique_num = 0, index = 0;

for ( counter; counter < N; counter++ )
{
    value = A[counter];

    if ( unique_array[value] < 0 )
    {
        unique_array[value] = value;
        unique_num ++;
    }
}

for ( counter = 0; counter < N; counter++ )
{
    value = A[counter];

    if ( unique_array[value] >= 0 )
    {
        unique_array[value] = -1;
        unique_num --;

        if ( unique_num == 0 )
            index = counter;
    }
}

return index;

}
4

1 に答える 1

1

配列のunique_array長さNは、ではなく、である必要がありN-1ます。

long unique_array[N]; // not N-1

さらにmemset、配列のすべての要素を-1;に設定しません。これを行うには、ループを使用します。

for ( counter = 0; counter < N; counter++ )
{
    unique_array[counter] = -1;
}

実際には、値ではなく、ビットの配列のみが必要longです。配列を0に初期化し、個々のエントリを次の代わりに1に設定できますvalue。

#define FALSE 0
#define TRUE 1
if ( unique_array[value] == FALSE )
{
    unique_array[value] = TRUE;
    unique_num ++;
}

この変更を行うと、明示的なループなしで配列を0に初期化できます。

int unique_array[N] = {0}; // this syntax only works with 0, not with -1
于 2012-11-21T19:14:39.713 に答える