C语言查找数组出现≥3次元素代码始终输出-1求助

题目要求 #

给定长度为n的数组，输出任意一个出现次数至少为3次的元素，不存在符合条件的元素则输出-1。

输入规则 #

• 第一行输入整数t (1≤t≤10^4)，代表测试用例数量；
• 每个测试用例第一行输入整数n (1≤n≤2⋅10^5)，代表当前测试用例的数组长度；
• 每个测试用例第二行输入n个整数a₁,a₂,…,aₙ (1≤aᵢ≤n)，即数组的各元素；
• 题目保证所有测试用例的n总和不超过2⋅10^5。

输出规则 #

对每个测试用例，输出任意一个出现次数≥3的元素，无符合条件元素则输出-1。

问题现象 #

对应实现的C语言代码运行时始终输出-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));
    }
}

错误原因 #

1. 结果被覆盖（直接导致始终输出-1）：遍历每个元素统计频次时，即使前面已经找到出现次数≥3的元素、给ptr[i]赋了正确值，后续遍历到其他频次不足3的元素时，会执行*(ptr+i) = -1把之前的正确结果覆盖。除非数组最后一个元素刚好是符合条件的元素，否则最终结果都会被覆盖为-1。
2. 时间复杂度严重超限：采用双重循环统计元素频次的时间复杂度为O(n²)，在题目给出的n最大2*10^5的数据规模下会直接运行超时，无法通过所有测试用例。
3. 频次数组设计冗余：frr数组按下标存储标记的统计逻辑绕弯，没有利用题目给出的aᵢ≤n的条件，增加了出错概率。

修正后代码 #

针对以上问题调整逻辑：找到符合条件的元素后直接记录结果避免覆盖，改用元素值直接作为索引的频次数组，把统计时间复杂度降到O(n)适配数据规模，修正后可正常运行的代码如下：

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int t, n, *arr, *freq, *res;
    scanf("%d", &t);
    res = (int*)malloc(t * sizeof(int));
    for (int i = 0; i < t; i++)
    {
        scanf("%d", &n);
        arr = (int*)malloc(n * sizeof(int));
        // 利用ai<=n的条件，开n+1长度的数组直接用元素值当下标统计频次，calloc自动初始化为0
        freq = (int*)calloc(n + 1, sizeof(int));
        int ans = -1;
        for (int j = 0; j < n; j++)
        {
            scanf("%d", arr + j);
            freq[arr[j]]++;
            // 元素出现次数达到3时直接记录答案，无需等全部遍历完成
            if (freq[arr[j]] == 3)
            {
                ans = arr[j];
            }
        }
        res[i] = ans;
        free(arr);
        free(freq);
    }
    for (int j = 0; j < t; j++)
    {
        printf("%d\n", res[j]);
    }
    free(res);
    return 0;
}

内容的提问来源于stack exchange，提问作者Ibrahim Yasser