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

是 3，因为序列[ A[0], A[1], A[2], A[3] ]等于[2, 2, 1, 0]，包含数组 A 中出现的所有值。

写一个函数

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应该有 length 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 回答