给定n个元素的数组a，打印任何出现至少三次的值，如果没有，则打印-1。

Question

这是我的代码，它总是输出-1，我不知道为什么。有什么帮助吗？输入第一行包含整数t (1≤t≤104) -测试用例数。

每个测试用例的第一行包含一个整数n (1≤n≤2⋅105) --数组的长度。

每个测试用例的第二行包含n个整数a1、a2、…。，a (1≤ai≤n) -数组的元素。

保证所有测试用例上n的和不超过2⋅105。

输出每个测试用例，打印任何至少三次出现的值，如果没有这样的值，则打印-1。

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n, size,*arr, *frr,count,*ptr,g,s;
    scanf("%d", &n);
    ptr = (int*)malloc(n * sizeof(int));
    for (int i = 0;i < n; i++)
    {
        scanf("%d",&size);
        arr = (int*)malloc(size * sizeof(int));
        frr = (int*)malloc(size * sizeof(int));
        for(int j = 0; j < size; j++)
            {
                scanf("%d",arr+j);
                *(frr + j) = -1;
            }
        if(size >= 3)
        {
            for (g = 0; g < size ; g++)
            {
                count=1;
                for(s = g + 1; s < size;s++)
                {
                    if(*(arr + g) == *(arr + s))
                    {
                        count++;
                        *(frr+s) = 0;
                    }             
                }
                if(*(frr+g) != 0 )
                {
                    *(frr+g) = count;
                }

                if(*(frr+g) >= 3)
                {
                    *(ptr+i) = *(arr + g);
                }else
                {
                    *(ptr+i) = -1;
                }
                
            }  
        }else
        {
            *(ptr+i) = -1;
        }
        
        free(arr);
        free(frr);

    }
    for(int j = 0;j<n;j++)
    {
        printf("%d\n",*(ptr+j));
    }
}

Answer 1

问题是，对于数组的每个元素，您都将*(ptr+i)设置为-1。这意味着数组中没有重复三次的稍后元素将*(ptr+i)重置为-1。

改变这个

            if(*(frr+g) >= 3)
            {
                *(ptr+i) = *(arr + g);
            }
            else
            {
                *(ptr+i) = -1;
            }

到这个

            if(*(ptr+i) == -1 && *(frr+g) >= 3)
            {
                *(ptr+i) = *(arr + g);
            }

在开始的时候加上

ptr = (int*)malloc(n * sizeof(int));
for (int i = 0;i < n; i++)
{
    *(ptr + i) = -1;

但是，正如在注释中已经说过的，您不需要ptr数组或frr数组。一次只运行一个测试，因此在打印出任何测试结果之前，不需要保留所有测试结果。您只需要保存正在测试的当前元素的频率，因此也不需要数组。

并使代码可读性，将*(arr + g)更改为arr[g]。他们俩的工作原理完全一样。

Answer 2

首先，这个数组分配

ptr = (int*)malloc(n * sizeof(int));

一点道理都没有。对于每个给定的数字序列，您可以立即输出该序列是否包含三个相等的元素，而无需将此信息存储在分配的数组中。

还分配这个辅助数组

frr = (int*)malloc(size * sizeof(int));

使代码不安全，效率低下。

如果找到一个已经发生了三次的元素，则遍历该数组是没有意义的。

否则，此代码段

            if(*(frr+g) >= 3)
            {
                *(ptr+i) = *(arr + g);
            }else
            {
                *(ptr+i) = -1;
            }

对于数组尾部中存在的元素，arr可能会错误地将值ptr[i]设置为-1，尽管在早期已经发现了前面的一个元素，该元素发生了三次。

没有指针ptr和frr所指向的冗余数组，程序可以如下所示

#include <stdio.h>
#include <stdlib.h>

int main( void )
{
    size_t t = 0;

    scanf( "%zu", &t );

    while (t--)
    {
        size_t n = 0;
        scanf( "%zu", &n );

        int result = -1;

        if (n)
        {
            int *a = malloc( n * sizeof( int ) );

            for (size_t i = 0; i < n; i++)
            {
                scanf( "%d", a + i );
            }

            for (size_t i = 2; result == -1 && i < n; i++)
            {
                int count = 1;
                for (size_t j = i; count != 3 && j-- != 0; )
                {
                    if (a[j] == a[i]) ++count;
                }

                if (count == 3) result = a[i];
            }

            free( a );
        }

        printf( "%d\n", result );
    }
}

Answer 3

我会完全以不同的方式处理这个问题。由于元素的范围没有显式限制，所以管理频率表有点棘手。但是每个测试数组中的最大元素数很小，因此

thrice

• 声明一个足够大的数组，足以容纳每个测试用例的所有测试用例

• 元素，
• 将所有元素读取到(1)数组
• 中，对数组进行排序(qsort()，或滚动您自己的插入或选择排序)H29H 110扫描排序数组，以方便地检测和报告至少出现的
• 值。